Séminaire de Cryptographie

Accueil     Présentation     Archives

Maxime Plançon

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.