REVIEW PAPER
REMARKS ON MULTIVARIATE EXTENSIONS OF POLYNOMIAL BASED SECRET SHARING SCHEMES
1
Polska Akademia Nauk w Warszawie
Publication date: 2014-12-05
SBN 2014;6(2): 285-297
KEYWORDS
Grobner basesChinese remainder theoremSecret Sharing Schemeaccessstructuremultivariate interpolation
ABSTRACT
We introduce methods that use Grobner 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
REFERENCES (21)
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¨obner bases, Proc. ISSAC’91, Bonn, ACM Press, 6469, New York 1991.
3.
T. Becker, V. Weispfenning, Gr¨obner 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¨obner 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¨obner 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-CRYPTO 2006, 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. Faugere ´ , A New Efficient Algorithm for Computing Gr¨obner Basis (F4), Journal of Pure and Applied Algebra 139(1-3), 6188, 1999.
12.
J.-C. Faugere ` , A new efficient algorithm for computing Gr¨obner 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.
16.
M. Mignotte, How to share a secret Cryptography. Springer Berlin Heidelberg, 371-375, 1983.
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¨obner 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.
| ISSN: | 2082-2677 |
We process personal data collected when visiting the website. The function of obtaining information about users and their behavior is carried out by voluntarily entered information in forms and saving cookies in end devices. Data, including cookies, are used to provide services, improve the user experience and to analyze the traffic in accordance with the Privacy policy. Data are also collected and processed by Google Analytics tool (more).
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
