How critical sets in Latin squares improve secret sharing reliability
Critical sets of Latin squares based on autoparatopisms
Cryptography and Security
Summary
The paper addresses a common problem in secret sharing schemes where some pieces of information are held by multiple people, making some holders indispensable to recover the secret. The authors use mathematical symmetries called autoparatopisms of Latin squares to organize these pieces of information into groups called orbits. By doing this, they create special critical sets that avoid overlapping dependencies. They test this method on small Latin squares and show how it can design better secret sharing methods.
What this means in practice
- •For cryptographic engineers: Design secret sharing schemes that reduce dependency on shared information holders by using critical sets based on Latin square symmetries.
- •For security protocol designers: Improve reliability of protocols distributing a secret among participants by leveraging structured critical sets to avoid indispensable holders.
Authors
Manuel González-Regadera, Raúl M. Falcón, María Dolores Frau
Abstract
In cryptography, critical sets of Latin squares have particularly been implemented to design secret sharing schemes. A main problem in these cryptographic protocols arises from absent holders of pieces of information that are common to different critical sets, because they become indispensable to recover the secret. This paper solves this problem by making use of the orbits of entries described by the autoparatopism group of the Latin square under consideration. To this end, we introduce the more general problem of computing critical sets of Latin squares having a given paratopism in their autoparatopism group. These critical sets depend only on the conjugacy class of the autoparatopism and the main class of the Latin square under consideration. Based on this fact, as an illustrative example, we determine the smallest and largest sizes of critical sets associated with autoparatopisms of Latin squares of order up to six. We implement this approach in the design of a new secret sharing scheme.