Paper 2025/2102

A Graph-Theoretic Framework for Randomness Optimization in First-Order Masked Circuits

Benedikt Gierlichs, COSIC, KU Leuven

Ingrid Verbauwhede, COSIC, KU Leuven

Abstract

We present a generic, automatable framework to reduce the demand for fresh randomness in first-order masked circuits while preserving security in the glitch-extended probing model. The method analyzes the flow of randomness through a circuit to establish security rules based on the glitch-extended probing model. These rules are then encoded as an interference graph, transforming the optimization challenge into a graph coloring problem, which is solved efficiently with a DSATUR heuristic. Crucially, the optimization only rewires randomness inputs without altering core logic, ensuring seamless integration into standard EDA flows and applicability to various gadgets like DOM-indep (Domain-Oriented Masking) and HPC (Hardware Private Circuits). On 32-bit adder architectures, the framework substantially reduces randomness requirements by 79–90%; for instance, the Kogge–Stone adder's requirement of 259 unique random inputs is reduced to 27. All optimized designs were evaluated using PROLEAD, with the leakage results indicating compliance with first-order glitch-extended probing security.

@misc{cryptoeprint:2025/2102,
      author = {Dilip Kumar S. V. and Benedikt Gierlichs and Ingrid Verbauwhede},
      title = {A Graph-Theoretic Framework for Randomness Optimization in First-Order Masked Circuits},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2102},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2102}
}