An Algebraic Approach for Evaluating Random Probing Security With Application to AES

Abstract

We employ an algebraic approach to estimate the success rate of a sidechannel adversary attacking secrets of a masked circuit within the Random Probing Model (RPM), where intermediate variables of the implementation leak with a probability p. Our method efficiently handles masked linear circuits, enabling security bound estimation for practically large masking orders. For non-linear circuits, we employ a linearization technique. To reason about the security of complex structures like an S-box, we introduce a composition theorem, reducing the RPM security of a circuit to that of its constituent gadgets. Moreover, we lower the complexity of the multiplication gadget of CHES 2016 from O(n² log(n)) to O(n²) while demonstrating its conjectured RPM security. Collectively, these novel methods enable the development of a practical masking scheme with O(n²) complexity for AES, maintaining security for a considerably high leakage rate p ≤ 0.02 ≈ 2^−5.6.