A Latin square autotopism secret sharing scheme (Q2630718)

In this article, the authors propose a scheme for sharing secrets based on Latin square autotopisms. Here, roughly speaking, is how the scheme works: An authority figure, called the dealer, begins with an autotopism \(\theta\) of a Latin square \(L\) and a contour \(C\) (a partial Latin square) with \((C,\theta)\) generating \(L\). The autotopism \(\theta\) is the secret that the dealer wishes to share. The dealer randomly expresses \(\theta\) as a product \(\sigma _1 \sigma _2\dots \sigma _\ell\) of permutations, and produces \(C_{\mathrm{public}}=\xi (C)= \sigma _\ell \sigma _{\ell-1}\dots \sigma _1 (C)\). The dealer identifies participants, \(\ell\) of them, and sends \(\sigma _i\) to the \(i\)-th participant. The dealer also makes \(C_{\mathrm{public}}\) public (though this is not absolutely necessary). At this point the dealer ends his/her knowledge of the transmission of the secret. Ultimately the secret is recovered by a compiler, who receives each \(\sigma _i\) from the participants and then computes a candidate \(\theta _{\mathrm{cand}}\) for \(\theta\) by putting \(\theta _{\mathrm{cand}}=\sigma_1 \sigma _2\dots \sigma _\ell\). Errors in transmission, etc., might result in incorrect transmission of the \(\sigma _i\) to the compiler. To check the viability of \(\theta _{\mathrm{cand}}\), the compiler can produce a contour \(C=\xi ^{-1}(C_{\mathrm{public}})\) where \(\xi =\sigma _\ell \sigma _{\ell-1}\dots \sigma _1\) is formed by the compiler using the \(\sigma _i\) that he/she has received. If this pair \((C,\theta _{\mathrm{cand}})\) generate a Latin square, then the compiler is quite certain that \(\theta _{\mathrm{cand}}=\theta\). The authors argue that this scheme avoids various drawbacks of previous Latin square secret sharing schemes, including security, the relatively large number of entries in a Latin square of order \(n\), difficulty in initialization, and difficulty in verification.