Gröbner Basis Cryptosystems
Tóm tắt
In the first sections we extend and generalize Gröbner basis theory to submodules of free right modules over monoid rings. Over free monoids, we adapt the known theory for right ideals and prove versions of Macaulay’s basis theorem, the Buchberger criterion, and the Buchberger algorithm. Over monoids presented by a finitely generated convergent string rewriting system we generalize Madlener’s Gröbner basis theory based on prefix reduction from right ideals to right modules. After showing how these Gröbner basis theories relate to classical group-theoretic problems, we use them as a basis for a new class of cryptosystems that are generalizations of the cryptosystems described in Barkee et al. (J Symb Comput 18, 497–501, 1994) and Fellows and Koblitz (Contemp Math 168, 51–61, 1994). Well known cryptosystems such as RSA, El-Gamal, Polly Cracker, Polly Two and a braid group cryptosystem are shown to be special cases. We also discuss issues related to the security of these Gröbner basis cryptosystems.
Tài liệu tham khảo
Anshel I., Anshel M., Goldfeld D. (1999) An algebraic method for public-key cryptography. Math Res Lett 6, 287–291
Barkee B., et al. (1994) Why you cannot even hope to use Gröbner bases in public key cryptography: an open letter to a scientist who failed and a challenge to those who have not yet failed. J Symb Comput 18, 497–501
Bluhm H. (2005) Syzygienberechnung in nichtkommutativen Polynomringen. Diplomarbeit, Universität Dortmund, Germany
Cheon, J.H., Jun, B. A polynomial time algorithm for the braid Diffie–Hellman conjugacy problem. In: Boneh, D. (ed.) Advances in cryptology – CRYPTO 2003. Lect Notes Comp Sci 2729, 212–225. Berlin Heidelberg New York: Springer (2003)
ElGamal T. (1985) A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans Inf. Theory 31, 469–472
Farkas D., Feustel C., Green E. (1993) Synergy in the theories of Gröbner bases and path algebras. Can J Math 45, 727–739
Farkas D., Green E., Kirkman E., Kuzmanovich J. (1993) Constructing projective resolutions. Commun Algebra 21, 1869–1887
Fellows M., Koblitz N. (1994) Combinatorial cryptosystems galore!. Contemp Math 168, 51–61
Geiselmann W., Steinwandt R. (2002) Cryptanalysis of Polly Cracker. IEEE Trans Inf Theory 48, 2990–2991
Green, E. Noncommutative Gröbner bases and projective resolutions. In: Dräxler, P. et al. (eds.) Computational methods for representations of groups and algebras. Proc. Euroconference Essen, Germany, 1–5 April 1997. Progress Math 173, 29–60. Basel Birkhüser (1999)
Green, E. Multiplicative bases, Gröbner bases, and right Gröbner bases J Symb Comput 29, 601–623 (2000)
Hofheinz D. (2003) Angriffe auf das Public-Key-System Polly Cracker. Studienarbeit, Universität Karlsruhe, Germany
Hofheinz, D., Steinwandt, R. A “differential” attack on Polly Cracker (extended abstract). In: Proceedings of the 2002 IEEE international symposium on information theory, p. 211
Ko, K.H., Lee, S.J., Cheon, J.H., Han, J.W., Kang, J.S., Park, C. New public-key cryptosystems using braid groups. In: Bellare, M. (ed.) Advances in cryptology – CRYPTO 2000, Lect Notes Comp Sci 1880, 166–183. Berlin Heidelberg New York: Springer 2000
Koblitz N. (1998) Algebraic aspects of cryptography, Algebra Computer and Mathemtics, Vol. 3. Springer, Heidelberg
Kreuzer M., Robbiano L. (2000) Computational commutative algebra 1. Springer, Berlin Heidelberg New York
Kreuzer, M., Robbiano, L. Computational commutative algebra 2. Berlin Heidelberg New York: Springer 2004 (in press)
Levy-dit-Vehel, F., Perret, L. A Polly Cracker system based on satisfiability. Progress Comp Sci Appl Logic 23, 177–192. Basel: Birkhäuser 2004
Ly L. (2003) Gröbner Basen und das Kryptoverfahren Polly Two. Dissertation, Universität Bochum, Germany
Ly, L. Polly two – a new algebraic polynomial-based public-key scheme, this volume
Madlener K., Otto F. (1998) Some applications of prefix-rewriting in monoids, groups, and rings. Reports on computer algebra, Vol. 22. Universität Kaiserlautern, Germany
Madlener K., Reinert B. (1993) Computing Gröbner bases in monoid and group rings. In: Bronstein M. (eds). Proc. Conf. ISSAC 1993 ACM Press, New York, pp. 254–263
Madlener K., Reinert B. (1998) Relating rewriting techniques on monoids and rings: congruences on monoids and ideals in monoid rings. Theor Comp Sci 208, 3–31
Madlener, K., Reinert, B. String rewriting and Gröbner bases – a general approach to monoid and group rings. In: Bronstein, M., Grabmeier, J., Weispfenning, V., (eds.) symbolic rewriting techniques, Proc. Workshop Monte Verita 1995. Progress Comp Sci Appl Logic 15, 127–150. Basel: Birkhäuser 1998
Mora, T. Gröbner bases for non-commutative polynomial rings. In: Calmet, J., (ed.) Proc. Conf. AAECC 3. Lect Notes Comp Sci 229, 353–362. Berlin Heidelberg New York: Springer 1986
Mora, T. Gröbner bases in non-commutative algebras, In: Gianni, P., (ed.) Proc. Conf. ISSAC 1988 Lect Notes Comp Sci 358, 150–161. Berlin Heidelberg New York: Springer 1989
Mora T. (1994) An introduction to commutative and noncommutative Gröbner bases. Theor Comp Sci 134, 131–173
Rai T. (2004) Infinite Gröbner bases and noncommutative Polly Cracker cryptosystems. Dissertation, Virginia Polytechnic Institute, Blacksburg
Reinert B. (1995) On Gröbner bases in monoid and group rings. Dissertation, Universität Kaiserslautern, Germany
Rivest R., Shamir A., Adleman L.N. (1978) A method for obtaining digital signatures and public key cryptosystems. Commun. ACM 21, 120–126