Paper 2026/151

Non-Complete Set Coverings for Higher Order Threshold Implementations

Abstract

Side-channel attacks (SCAs) represent an important threat for the implementation of cryptographic algorithms. These attacks exploit the information leakage found in the physical magnitudes of hardware devices (e.g. current draw, electromagnetic emanation). Threshold Implementations (TIs) aim to mitigate SCAs by implementing a modified version of the algorithm that operates over randomized shares of its input and intermediate values. This strategy relies on the possibility of splitting the algorithm to be protected into sub-functions that satisfy certain properties about their dependence structure on the randomized shares. Non-complete set coverings (NCSCs) are combinatorial objects that can provide this dependence structure and guide the design of TIs. Given the desired order of protection $d$ and the algebraic degree $t$ of the functions to be implemented, for an NCSC to be useful, its cardinality $r$ should be small and similar to the number of input shares $s$. This work contributes to the study of NCSCs for efficient TIs by finding smaller coverings and proving novel theoretical bounds on their cardinality. We present a new NCSC for the case $t=3,d=2$ that is optimal and NCSCs for the cases $t=3,d=3$ and $t=4,d=2$ whose sizes are close to the lower bounds. We also present new combinatorial properties of these coverings and an algorithm for the search of small NCSCs.