Amortizing Randomness Complexity in Private Circuits

Cryptographic implementations are vulnerable to Side Channel Analysis (SCA), where an adversary exploits physical phenomena such as the power consumption to reveal sensitive information. One of the most widely studied countermeasures against SCA are masking schemes. A masking scheme randomizes intermediate values thereby making physical leakage from the device harder to exploit. Central to any masking scheme is the use of randomness, on which the security of any masked algorithm heavily relies. But since randomness is very costly to produce in practice, it is an important question whether we can reduce the amount of randomness needed while still guaranteeing standard security properties such as t-probing security introduced by Ishai, Sahai and Wagner (CRYPTO 2003). In this work we study the question whether internal randomness can be re-used by several gadgets, thereby reducing the total amount of randomness needed. We provide new techniques for masking algorithms that significantly reduce the amount of randomness and achieve better overall efficiency than known constructions for values of t that are most relevant for practical settings.