Weyl Gröbner Basis Cryptosystems

  • In this thesis, we shall consider a certain class of algebraic cryptosystems called Gröbner Basis Cryptosystems. In 1994, Koblitz introduced the Polly Cracker cryptosystem that is based on the theory of Gröbner basis in commutative polynomials rings. The security of this cryptosystem relies on the fact that the computation of Gröbner basis is, in general, EXPSPACE-hard. Cryptanalysis of these commutative Polly Cracker type cryptosystems is possible by using attacks that do not require the computation of Gröbner basis for breaking the system, for example, the attacks based on linear algebra. To secure these (commutative) Gröbner basis cryptosystems against various attacks, among others, Ackermann and Kreuzer introduced a general class of Gröbner Basis Cryptosystems that are based on the difficulty of computing module Gröbner bases over general non-commutative rings. The objective of this research is to describe a special class of such cryptosystems by introducing the Weyl Gröbner Basis Cryptosystems. We divide this class of cryptosystems in two parts namely the (left) Weyl Gröbner Basis Cryptosystems and Two-Sided Weyl Gröbner Basis Cryptosystems. We suggest to use Gröbner bases for left and two-sided ideals in Weyl algebras to construct specific instances of such cryptosystems. We analyse the resistance of these cryptosystems to the standard attacks and provide computational evidence that secure Weyl Gröbner Basis Cryptosystems can be built using left (resp. two-sided) Gröbner bases in Weyl algebras.

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Author:Rashid Ali
Advisor:Martin Kreuzer
Document Type:Doctoral Thesis
Year of Completion:2011
Date of Publication (online):2011/06/22
Publishing Institution:Universität Passau
Granting Institution:Universität Passau, Fakultät für Informatik und Mathematik
Date of final exam:2011/06/16
Release Date:2011/06/22
Tag:Non commutative Gröbner Basis; Public Key Cryptosystem
GND Keyword:Gröbner-Basis; Kryptologie; Weyl-Algebra
Institutes:Fakultät für Informatik und Mathematik / Mitarbeiter Lehrstuhl/Einrichtung der Fakultät für Informatik und Mathematik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Licence (German):License LogoStandardbedingung laut Einverständniserklärung

$Rev: 13581 $