Remarks on the Classical Threshold Secret Sharing Schemes

• Autorzy: Spież S. , Srebrny M. , Urbanowicz J.
• Języki publikacji: EN

Abstrakty

EN

We survey some results related to classical secret sharing schemes defined in Shamir [10] and Blakley [1], and developed in Brickell [2] and Lai and Ding [4]. Using elementary symmetric polynomials, we describe in a unified way which allocations of identities to participants define Shamir’s threshold scheme, or its generalization by Lai and Ding, with a secret placed as a fixed coefficient of the scheme polynomial. This characterization enabled proving in Schinzel et al. [8], [9] and Spie˙z et al. [13] some new and non-trivial properties of such schemes. Also a characterization of matrices corresponding to the threshold secret sharing schemes of Blakley and Brickell’s type is given. Using Gaussian elimination we provide an algorithm to construct all such matrices which is efficient in the case of relatively small matrices. The algorithm may be useful in constructing systems where dynamics is important (one may generate new identities using it). It can also be used to construct all possible MDS codes.

Słowa kluczowe

EN

secret sharing; finite fields; generalized Vandermonde determinants; elementary symmetric polynomials; Gaussian elimination; threshold access structure; MDS codes; (k -1, k)-bases

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 114, nr 3/4
• Strony: 345--357
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Spież S.

autor

Srebrny M.

autor

Urbanowicz J.

• Institute of Mathematics, Polish Academy of Sciences, ul. Śniadeckich 8, P.O. Box 21, 00-956 Warsaw, Poland,

Bibliografia

• [1] G.R. Blakley, Safeguarding cryptographic keys, AFIPS Confer. Proc. 48 (1979), 313-317.
• [2] E.F. Brickell, Some ideal secret sharing schemes, J. Combin. Math. Combin. Comput. 9 (1989), 105-113.
• [3] R.J. Evans and I.M. Isaacs, Generalized Vandermonde determinants and roots of unity of prime order, Proc. Amer. Math. Soc. 58 (1976), 51-54.
• [4] C.-P. Lai and C. Ding, Several generalizations of Shamir's secret sharing scheme, Internat. J. Found. Comput. Sci. 15 (2004), 445-458.
• [5] R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications 20 (G.-C. Rota, ed.), Cambridge Univ. Press, Cambridge, 2008, digitally printed version.
• [6] F.J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland Math. Library 16 (1977).
• [7] T. Muir, A Treatise on the Theory of Determinants, Dover Publ., New York 1960.
• [8] A. Schinzel, S. Spie˙z and J. Urbanowicz, Admissible tracks in Shamir's scheme, Finite Fields and Their Applications 16 (2010), 449-462, or: preprint http://www.impan.pl/Preprints/p707.pdf.
• [9] A. Schinzel, S. Spie˙z and J. Urbanowicz, Elementary symmetric polynomials in Shamir's scheme, J. Number Theory 130 (2010), 1572-1580.
• [10] A. Shamir, How to share a secret, Comm. ACM 22 (1979), 612-613.
• [11] V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge Univ. Press, Cambridge, 2005.
• [12] S. Spiez, M. Srebrny and J. Urbanowicz, Secret sharing matrices, preprint http://www.impan.pl/Preprints/p708.pdf.
• [13] S. Spie˙z, A. Timofeev and J. Urbanowicz, Non-admissible tracks in Shamir's scheme, Finite Fields and Their Applications 17 (2011), 329-342.
• [14] D.R. Stinson, Cryptography, Theory and Practice, CRC Press, Boca Raton, 1995.
• [15] T. Tassa and J.L. Villar, On proper secrets, (t, k)-bases and linear codes, Des. Codes Cryptogr. 52 (2009), 129-154.