Non-commutative Groebner Bases in Cryptography
by
Lothar Gerritzen
University of Bochum

Non-commutative Groebner Bases in Cryptography

An non-commutative version of the cryptosystem Polly Two by Le Van Ly which is a sophisticated form based on the idea of the general algebraic public-key cryptosystem called Polly Cracker introduced in 1994 by Fellows and Koblitz. The public key is an ideal I in the non-commutative polynomial ring in several variables over a finite field F and a subset g₁, ...g_r of normal forms with respect to I. The secret key is the Groebner bases G of I. In order to encrypt a message m Î Fg₁ + ..+ Fg_r one is choosing randomly a polynomial f in I and computes the cipher text c = f + m. The decryption of c is the reduction of c relative to G. One has to defend against various forms of intelligent linear algebra attacks which makes it difficult to suggest effective versions. We will discuss some advantages of this non-commutative system and suggest to consider also RSA over quaternions.

Date received: March 15, 2005