Paper 2023/1182

Long Paper: Provable Secure Parallel Gadgets

Francesco Berti, Bar-Ilan University
Sebastian Faust, TU Darmstadt
Maximilian Orlt, TU Darmstadt

Side-channel attacks are a fundamental threat to the security of cryptographic implementations. One of the most prominent countermeasures against side-channel attacks is masking, where each intermediate value of the computation is secret shared, thereby concealing the computation's sensitive information. An important security model to study the security of masking schemes is the random probing model, in which the adversary obtains each intermediate value of the computation with some probability $p$. To construct secure masking schemes, an important building block is the refreshing gadget, which updates the randomness of the secret shared intermediate values. Recently, Dziembowski, Faust, and Zebrowski (ASIACRYPT'19) analyzed the security of a simple refreshing gadget by using a new technique called the leakage diagram. In this work, we follow the approach of Dziembowski et al. and significantly improve its methodology. Concretely, we refine the notion of a leakage diagram via so-called dependency graphs, and show how to use this technique for arbitrary complex circuits via composition results and approximation techniques. To illustrate the power of our new techniques, as a case study, we designed provably secure parallel gadgets for the random probing model, and adapted the ISW multiplication such that all gadgets can be parallelized. Finally, we evaluate concrete security levels, and show how our new methodology can further improve the concrete security level of masking schemes. This results in a compiler provable secure up to a noise level of $ O({1})$ for affine circuits and $ O({1}/{{n^n}})$ in general.

Note: This version has been revised to address a bug in the security analysis for general circuits.

Available format(s)
Publication info
A major revision of an IACR publication in TCHES 2023
Contact author(s)
maximilian orlt @ tu-darmstadt de
2023-12-22: revised
2023-08-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Francesco Berti and Sebastian Faust and Maximilian Orlt},
      title = {Long Paper: Provable Secure Parallel Gadgets},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1182},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.