In 1994, Moss Sweedler’s dog proposed a cryptosystem, known as Barkee’s Cryptosystem, and the related cryptanalysis. Its explicit aim was to dispel the proposal of using the urban legend that “Gröbner bases are hard to compute”, in order to devise a public key cryptography scheme. Therefore he claimed that “no scheme using Gröbner bases will ever work”. Later, further variations of Barkee’s Cryptosystem were proposed on the basis of another urban legend, related to the infiniteness (and consequent uncomputability) of non-commutative Gröbner bases; unfortunately Pritchard’s algorithm for computing (finite) non-commutative Gröbner bases was already available at that time and was sufficient to crash the system proposed by Ackermann and Kreuzer. The proposal by Rai, where the private key is a principal ideal and the public key is a bunch of polynomials within this principal ideal, is surely immune to Pritchard’s attack but not to Davenport’s factorization algorithm. It was recently adapted specializing and extending Stickel’s Diffie–Hellman protocols in the setting of Ore extension. We here propose a further generalization and show that such protocols can be broken simply via polynomial division and Buchberger reduction.

Why you cannot even hope to use Gröbner bases in cryptography : an eternal golden braid of failures / B. Barkee, M. Ceria, T. Moriarty, A. Visconti. - In: APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING. - ISSN 0938-1279. - 31:3-4(2020 Jun), pp. 235-252.

Why you cannot even hope to use Gröbner bases in cryptography : an eternal golden braid of failures

M. Ceria
;
A. Visconti
2020

Abstract

In 1994, Moss Sweedler’s dog proposed a cryptosystem, known as Barkee’s Cryptosystem, and the related cryptanalysis. Its explicit aim was to dispel the proposal of using the urban legend that “Gröbner bases are hard to compute”, in order to devise a public key cryptography scheme. Therefore he claimed that “no scheme using Gröbner bases will ever work”. Later, further variations of Barkee’s Cryptosystem were proposed on the basis of another urban legend, related to the infiniteness (and consequent uncomputability) of non-commutative Gröbner bases; unfortunately Pritchard’s algorithm for computing (finite) non-commutative Gröbner bases was already available at that time and was sufficient to crash the system proposed by Ackermann and Kreuzer. The proposal by Rai, where the private key is a principal ideal and the public key is a bunch of polynomials within this principal ideal, is surely immune to Pritchard’s attack but not to Davenport’s factorization algorithm. It was recently adapted specializing and extending Stickel’s Diffie–Hellman protocols in the setting of Ore extension. We here propose a further generalization and show that such protocols can be broken simply via polynomial division and Buchberger reduction.
Barkee’s cryptosystem; Buchberger Theory; Polly Cracker; Stickel’s protocol
Settore MAT/02 - Algebra
giu-2020
Article (author)
File in questo prodotto:
File Dimensione Formato  
GBCrypto_preprint.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 147.46 kB
Formato Adobe PDF
147.46 kB Adobe PDF Visualizza/Apri
Barkee2020_Article_WhyYouCannotEvenHopeToUseGröbn.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 2.17 MB
Formato Adobe PDF
2.17 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/742753
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact