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.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.