Date de l'exposé : 03 février 2023
Exploiting algebraic structures in probing security (eprint 2022/1540)
The so-called ω-encoding, introduced by Goudarzi, Joux and
Rivain (Asiacrypt 2018), generalizes the commonly used arithmetic en-
coding. By using the additionnal structure of this encoding, they pro-
posed a masked multiplication gadget (GJR) with quasilinear (random-
ness and operations) complexity. A second contribution by Goudarzi,
Prest, Rivain and Vergnaud in this line of research appeared in TCHES
2021. The authors revisited the aforementioned multiplication gadget
(GPRV), and brought the IOS security notion for refresh gadgets to al-
low secure composition between probing secure gadgets.
In this paper, we propose a follow up on GPRV. Our contribution stems
from a single Lemma, linking algebra and probing security for a wide
class of circuits, further exploiting the algebraic structure of ω-encoding.
On the theoretical side, we weaken the IOS notion into the KIOS notion,
and we weaken the usual t-probing security into the RTIK security. The
composition Theorem that we obtain by plugging together KIOS, RTIK
still achieves region-probing security for composition of circuits.
To substantiate our weaker definitions, we also provide examples of com-
petitively efficient gadgets verifying our weaker security notions. Explic-
itly, we give 1) a refresh gadget that uses d-1 random field elements
to refresh a length d encoding that is KIOS but not IOS, and 2) multi-
plication gadgets asymptotically subquadratic in both randomness and
complexity. While our algorithms outperform the ISW masked compiler
asymptotically, their security proofs require a bounded number of shares
for a fixed base field.
