Paper 2026/2796
Applying Combinatorial Techniques To Find Minimal Non-Complete Set Coverings
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
-
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}
}