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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$t=3,d=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>=</mo> <mn>3</mn> <mo>,</mo> <mi>d</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> that is optimal and NCSCs for the cases <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$t=3,d=3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>=</mo> <mn>3</mn> <mo>,</mo> <mi>d</mi> <mo>=</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$t=4,d=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>=</mo> <mn>4</mn> <mo>,</mo> <mi>d</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> 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.

Non-complete set coverings for higher order threshold implementations

期刊论文
出版模式：

开放获取
发表日期：

2026年5月16日

查看全文

Oriol Farràs,
Óscar Fidalgo,
Carlos Andres Lara-Nino

摘要

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$ $t = 3, d = 2$ that is optimal and NCSCs for the cases $t=3,d=3$ $t = 3, d = 3$ and $t=4,d=2$ $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.