Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleGr\"obner basis cryptosystems.
Author(s) Peter Ackermann, Martin Kreuzer
TypeArticle in Journal
AbstractIn 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.
KeywordsGröbner basis, Cryptosystem, Monoid ring
ISSN0938-1279; 1432-0622/e
URL http://link.springer.com/article/10.1007%2Fs00200-006-0002-0
JournalAppl. Algebra Eng. Commun. Comput.
PublisherSpringer, Berlin/Heidelberg
Translation No
Refereed No