Paper 2017/869

Amortizing Randomness Complexity in Private Circuits

Sebastian Faust, Clara Paglialonga, and Tobias Schneider


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.

Note: This is a major revision. In particular, we fixed a flaw in one of our constructions.

Available format(s)
Publication info
A major revision of an IACR publication in ASIACRYPT 2017
side-channel attacksmasking schemesrandomness
Contact author(s)
clara paglialonga @ crisp-da de
2018-04-26: revised
2017-09-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sebastian Faust and Clara Paglialonga and Tobias Schneider},
      title = {Amortizing Randomness Complexity in Private Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2017/869},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.