Critical and forcing sets related to the autotopism group of a Latin square

Abstract

In Cryptography, critical sets of any Latin square L can be used to get the access structure of a secret sharing scheme [2, 6] having triples of L as shares. In such a scheme, further information about the symmetry of L can be obtained by keeping in mind the autotopism group U(L) [4]. Because the size of an autotopism is generally much larger than that of a triple of L, we propose in this paper an algorithm which allows to decompose any principal autotopism Θ ∈ U(L) into triples of a partial Latin square PΘ. Critical sets of PΘ are then used to define the access structure of the new scheme. In this way, we propose an algorithm depending on the order of L which allows to give an upper bound of the size of the smallest set of triples equivalent to Θ. Finally, as Latin squares of order n are equivalent to perfect matchings of Kn,n [1], we relate the previous critical sets with the forcing sets of the perfect matching associated to L. A classification of these forcing sets is then obtained.