Remarks on multivariate extensions of polynomial based secret sharing schemes

• Autorzy: Derbisz J.

Warianty tytułu

PL

Uwagi na temat wielowymiarowych rozszerzeń schematów podziału sekretu opartych na wielomianach

• Języki publikacji: EN

Abstrakty

EN

We introduce methods that use Gröbner bases for secure secret sharing schemes. The description is based on polynomials in the ring R = K[X1,...,Xl] where identities of the participants and shares of the secret are or are related to ideals in R. Main theoretical results are related to algorithmical reconstruction of a multivariate polynomial from such shares with respect to given access structure, as a generalisation of classical threshold schemes. We apply constructive Chinese remainder theorem in R of Becker and Weispfenning. Introduced ideas find their detailed exposition in our related works.

PL

Wprowadzamy metody wykorzystujące bazy Gröbnera do schematów podziału sekretu. Opis bazuje na wielomianach z pierścienia R = K[X1,...,Xl], gdzie tożsamości użytkowników oraz ich udziały są lub są związane z ideałami w R. Główne teoretyczne rezultaty dotyczą algorytmicznej rekonstrukcji wielomianu wielu zmiennych z takich udziałów zgodnie z zadaną (dowolną) strukturą dostępu, co stanowi uogólnienie klasycznych schematów progowych. W pracy wykorzystujemy konstruktywną wersję Chińskiego twierdzenia o resztach w pierścieniu R pochodzącą od Beckera i Weispfenninga. Wprowadzone idee znajdują swój szczegółowy opis w naszych związanych z tym tematem pracach.

Słowa kluczowe

EN

Gröbner bases; Chinese remainder theorem; secret sharing scheme; access structures; multivariate interpolation

PL

bazy Gröbnera; chińskie twierdzenie o resztach; schemat podział sekretu; systemy dostępowe; interpolacja wielowymiarowa

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Studia Bezpieczeństwa Narodowego
• Rocznik: 2014
• Tom: R. 4, Nr 6
• Strony: 285--297
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Derbisz J.

• Institute of Computer Science Polish Academy of Sciences’ fellowship for postdoctoral researchers

Bibliografia

• [1] C. Asmuth, J. Bloom, A modular approach to key safeguarding, IEEE Trans. on Information Theory, IT-29(2):208-211, 1983.
• [2] T. Becker, V. Weispfenning, The Chinese remainder problem, multivariate interpolation, and Gröbner bases, Proc. ISSAC’91, Bonn, ACM Press, 6469, New York 1991.
• [3] T. Becker, V. Weispfenning, Gröbner Bases: A Computational Approach to Commutative Algebra, Springer-Verlag, 1993.
• [4] M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, 1-10, Proc. ACM STOC ’88.
• [5] G. Blakley, Safeguarding cryptographic keys, Proceedings of the National Computer Conference 48: 313–317, 1979
• [6] E.F. Brickell, Some ideal secret sharing schemes, J. Combin. Math. Combin. Comput. 9, 105-113, 1989.
• [7] B. Buchberger, Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory, N. K. Bose ed. Recent trends in Multidimensional System theory. Dordrecht: Reidel, 184-232, 1985.
• [8] B. Buchberger, F. Winkler, Gröbner Bases and Applications, Cambridge University Press 1998.
• [9] H. Chen, R. Cramer, Algebraic geometric secret sharing schemes and secure multi-party computations over small fields, Advances in Cryptology-CRYPTO2006,Springer-Berlin-Heidelberg,521-536,2006.
• [10] J. Derbisz, Methods of encrypting monotonic access structures, Annales UMCS Informatica AI XI, 2, 49-60, 2011.
• [11] J.-C. Faugére, A New Efficient Algorithm for Computing Gröbner Basis (F4), Journal of Pure and Applied Algebra 139(1-3), 6188, 1999.
• [12] J.-C. Faugére, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), in: ISSAC 02: Proceedings from the International Symposium on Symbolic and Algebraic Computation, pp. 7583, 2002.
• [13] M. Fellows, N. Koblitz, Combinatorial cryptosystems galore!, Contemporary Mathematics, 51-61, 1994.
• [14] M. Gasca, T. Sauer, Polynomial interpolation in several variables, Adv. Comput. Math., 12 (4), 377–410, 2000.
• [15] N. Koblitz, Algebraiczne aspekty kryptografii, WNT, Warszawa 2000.
• [16] M. Mignotte, How to share a secret Cryptography. Springer Berlin Heidelberg, 371-375, 1983.
• [17] P.J. Olver, On multivariate interpolation, Stud. Appl. Math. 116, 201-240, 2006.
• [18] O. Ore, The general Chinese remainder theorem, American Mathematical Monthly, 59:365-370, 1952.
• [19] T. Sauer, Polynomial interpolation of minimal degree and Gröbner bases, Groebner Bases and Applications (Proc. of the Conf. 33 Years of Groebner Bases), eds. B. Buchberger and F. Winkler, London Math. Soc. Lecture Notes, Vol. 251, 483–494 Cambridge University Press, 1998.
• [20] A. Shamir, How to share a secret, Communications of the ACM 22 (11): 612613, 1979.
• [21] T. Tassa, N. Dyn, Multipartite Secret Sharing by Bivariate Interpolation, ICALP (2), 288-299, 2006.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).