Paper 2026/2796

Applying Combinatorial Techniques To Find Minimal Non-Complete Set Coverings

Enrico Piccione, Ruhr University Bochum
Jan Vorloeper, Ruhr University Bochum
Abstract

One of the most prominent hardware countermeasures against side-channel attacks are threshold implementations (TIs). The technique uses masking to split the operations in a cryptographic algorithm into several ones operating on shares. The coverage and non-completeness requirements of TIs are mathematically described by the notion of non-complete set coverings (NCSCs). Importantly, the number of members inside an NCSC determines the number of output shares and therefore directly impacts the complexity of the resulting TI. In this work, we derive new lower bounds on the minimal number of members of NCSCs and obtain new upper bounds by explicit constructions. We present a group-theoretic construction of balanced NCSCs, in which the numbers of input and output shares coincide, together with a search algorithm based on intersections of group translates. Our methods determine the smallest balanced coverings in two previously unresolved cases and yield exact minima and classifications of optimal coverings for an infinite family of parameters. These results resolve all four explicit open problems posed by Farr\`as, Fidalgo and Lara-Nino.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Threshold ImplementationsNon-Complete Set Coverings
Contact author(s)
enrico piccione @ rub de
jan vorloeper @ rub de
History
2026-11-09: approved
2026-11-06: received
See all versions
Short URL
https://ia.cr/2026/2796
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2796,
      author = {Enrico Piccione and Jan Vorloeper},
      title = {Applying Combinatorial Techniques To Find Minimal Non-Complete Set Coverings},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2796},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2796}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.