nach oben

Applicable Algebra in Engineering, Communication and Computing

Erschienen in:

17.04.2020 | Original Paper

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

verfasst von: Boo Barkee, Michela Ceria, Theo Moriarty, Andrea Visconti

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 3-4/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel HELP: a sparse error locator polynomial for BCH codes

Nächster Artikel A trigonometric approach for Dickson polynomials over fields of characteristic two

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

To be chosen e.g in the set

$$\begin{aligned} {\mathcal{A}} := X \cup \{x_ix_j^{-1} : x_i,x_j\in X\}\cup \{x_ix_j : x_i,x_j\in X\} \cup \{x_ix_jx_i^{-1}x_j^{-1} : x_i,x_j\in X\}. \end{aligned}$$

which perhaps could be true if, instead of using the most efficient implementations [32, 35] of Buchberger’s algorithm [8, 9] based on Möller Lifting Theorem [50], the decypher applies the obsolete S-polynomial test/completion [10], but is definitely false if Gröbner bases are produced either with Macaulay-like algorithms [43, 44] as Faugère’s $F_4$ [26] and $F_5$ [27] or with involutive algorithms [33, 34] based on Janet theory [40].

Given a finite set of terms $m_1,\ldots ,m_r\in \mathcal {T}$ let us construct, by repeated GCDs, a finite sequence— a sequence and not just a set—$M := [n_1,\ldots ,n_s] \subset \mathcal {T}$ and subsets $J_i \subset \{1,\ldots ,s\}$$1\le i \le r,$ such that

for each $i, 1\le i \le r,$$m_i = \prod \nolimits _{l\in J_i} n_l$;
for each $i,j, 1\le i < j \le r,$$\mathrm{lcm}(m_i,m_j) = \prod \nolimits _{l\in J_i\cup J_j} n_l.$

Now let us choose, for each $l, 1 \le l \le s$, an element $h_l\in {\mathcal{P}}$ such that $\mathbf{T}(h_l) < n_l$ and let us define

$\gamma _l := n_l-h_l,$ for each $l, 1 \le l \le s,$
$g_i := \prod \nolimits _{l\in J_i} \gamma _l,$ for each $i, 1\le i \le r.$

Then $G = \{g_i. 1\le i\le r\}$ is a Gröbner basis such that $\mathbf{T}(G) = (m_1,\ldots ,m_r)$.

${\mathcal{O}}(\mathsf{T}^4(\delta ))$ where $\delta := \max (\deg (\tau ) : \tau \in \mathbf{G}_\prec (\mathsf{I}) = {\mathcal{O}}(d^{n2^n}).$

notwithstanding that Pritchard [58] had already formulated an adaptation of the Fantomas Attack

If the sequence is finite $F := \{f_i,u\ge i \ge 1\}$ we can simply set, for each $i>u$ either $f_i:=0$ or $f_i:=f_u$.

id est a term ordering $\prec$ on $\mathcal {T}^m$ is called sequential if for each $\tau \in \langle X_1,\ldots ,X_n\rangle ^m$ the set $\{\omega \in \langle X_1,\ldots ,X_n\rangle : \omega \prec \tau \}^m$ is finite.

Ackermann, P., Kreuzer, M.: Gröbner basis cyptosystems. J. Appl. Alg. 17, 173–194 (2006)MATH

Albrecht, M.R., Farshim, P., Faugère, J.-C., Perret, L.: Polly Cracker, Revisited. L.N.C.S 7073, 179–196 (2011)MathSciNetMATH

Albrecht, M.R., Farshim, P., Faugère, J.-C., Perret, L.: Polly Cracker, revisited. Des. Codes Cryptogr. 79, 261–302 (2016)MathSciNetCrossRef

Alonso, M.E., Marinari, M.G., Mora, T.: Oracle-supported drawing of the Gröbner éscalier”. preprint (2008)

Backelin, J., Cojocaru, S., Ufnarovski, V.: Mathematical Computations using Bergman Lund University

Barkee, B., Can, D.C., Ecks, J., Moriarty, T., Ree, R.F.: Why you cannot even hope to use Gröbner Bases in Public Key Cryptography. J. Symb. Comp. 18, 497–501 (1994)CrossRef

Billet, O., Patarin, J., Seurin, Y.: Analysis of Intermediate Field Systems, eprint iacr 542 (2009)

Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Ph. D. Thesis, Innsbruck (1965)

Buchberger, B.: Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleischunssystem. Aeq. Math. 4, 374–383 (1970)CrossRef

10.

Buchberger, B.: A Criterion for Detecting Unnecessary Reduction in the Construction of Gröbner bases. L.N.C.S 72, 3–21 (1979)MATH

11.

Buchberger, B.: Miscellaneours Results on Groebner Bases for Polynomial Ideals II. Technical Report 83/1, University of Delaware, Department of Computer and Information Sciences, p. 31 (1983)

12.

Buchberger, B.: Gröbner bases computation by triangularizing Macaulay matrices. The 50th Anniversary of Gröbner Bases. Mathematical Society of Japan (2018)

13.

Bulygin, S.: Chosen-cyphertext attack on noncommutative Polly Cracker. arXiv:abs/cs/0508015

14.

Burger, R., Heinle, A.: A Diffie-Hellman-like key exchange protocol based on multivariate Ore polynomials. preprint (2014). arXiv:1407.1270.pdf

15.

Caboara, M., Caruso, F., Traverso, C.: Gröbner bases for public key cryptography. To appear on ACM Press, New York, ISSAC 08: Proceedings of the 2008 International Symposium on Symbolic and Algebraic Computation

16.

Caboara, M., Caruso, F., Traverso, C.: Block lattice polly cracker, theory and practice. Second Workshop on Mathematical Cryptology, Santander, 24-27 Ottobre (2008). pp. 75–82. [Extended Abstract]

17.

Caboara, M., Caruso, F., Traverso, C.: Heterogeneous lattice metrics and the NTWO cryptosystem Second Workshop on Mathematical Cryptology , Santander, 24-27 Ottobre (2008). pp. 118–121

18.

Caboara, M., Caruso, F., Traverso, C.: Block Lattice Polly Cracker: design, implementation and security. J. Symb. Comput. 46(5), 534–549 (2011)CrossRef

19.

Cao, Z., Dong, X., Wang, L.: New Public Key Cryptosystems using polynomials over Non-commutative rings, Cryptology e-print Archive, 2007. https://eprint.iacr.org/2007/009.pdf

20.

Caruso, F.: Factorization of Non-Commutative Polynomials (2010). arXiv:1002.3180

21.

Ceria, M., Mora, T.: Buchberger–Zacharias theory of multivariate Ore extensions. J. Pure Appl. Algebra 221(12), 2974–3026 (2017)MathSciNetCrossRef

22.

Ceria, M., Moriarty, T., Visconti, A.: Why you should not even think to use Ore algebras in Cryptography. https://www.researchgate.net/publication/335608455_Why_you_should_not_even_think_to_use_Ore_algebras_in_Cryptography

23.

Cojocaru, S., Ufnarovski, V.: Noncommuatative Gröbner basis, Hilbert series, Anick’s resolution and BERGMAN under MS-DOS. Comput. Sci. J. Moldova 3, 24–39 (1995)

24.

Dickenstein, A., Fitchas, N., Giusti, M., Sessa, C.: The membership problem for unmixed polynomial ideals is solvable in single exponential time. Discrete Appl. Math. 33, 73–94 (1991)MathSciNetCrossRef

25.

Dubé, T.W.: The Structure of Polynomial Ideals and Gröbner Bases SIAM J. Comput. 19(4) (2006)

26.

Faugère, J.-C.: A new efficient algorithm for computating Gröbner bases ($F_4$). J. Pure Appl. Algebra 139, 61–88 (1999)MathSciNetCrossRef

27.

Faugère, J.-C.: A new efficient algorithm for computating Gröbner bases without reduction to zero ($F_5$), Proc. ISSAC 2002, 75–83, ACM (2002)

28.

J-C.Faugère, A. Joux, Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems using Grobner Bases, In Dan Boneh, editor, Ad-vances in Cryptology—CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science. UK: Springer, pp. 44–60 (2003)

29.

Fellows, M.R., Koblitz, N.: Kid krypto. Advances in Cryptography - Crypto’92. Lect. N. Comp. Sci. 740, 371–389 (1993)CrossRef

30.

Fellows, M.R., Koblitz, N.: Combinatorially based cryptography for children (and adults). Congressus Numer. 99, 9–41 (1994)MathSciNetMATH

31.

Fellows, M.R., Koblitz, N.: Combinatorial cryptosystems galore!. Contempor. Math. 168, 51–61 (1994)MathSciNetCrossRef

32.

Gebauer, R., Möller, H.M.: On an Installation of Buchbgerger’s Algorithm. J. Symb. Comp. 6, 275–286 (1988)CrossRef

33.

Gerdt, V.P., Blinkov, Y.A.: Involutive bases of polynomial ideals. Math. Comp. Simul. 45, 543–560 (1998)MathSciNetCrossRef

34.

Gerdt, V.P., Blinkov, Y.A.: Minimal involutive bases. Math. Comp. Simul. 45, 519–541 (1998)MathSciNetCrossRef

35.

Giovini, A., et al.: “One sugar cube, please” OR Selection strategies in the Buchberger algorithm, Proc. ISSAC ’91, 49–54, ACM (1991)

36.

Green, E.L., Mora, T., Ufnarovski, V.: The non-commutative Gröbner freaks. Progress Comput. Sci. Appl. Logic 15, 93–104 (1991). BirkhäuserMATH

37.

Hermann, G.: Die Frage der endlich vielen Schritte in die Theorie der Polynomideale. Math. Ann. 95, 736–788 (1926)MathSciNetCrossRef

38.

Kandri-Rody, A., Weispfenning, W.: Non-commutative Gröbner Bases in Algebras of Solvable Type. J. Symb. Comp. 9, 1–26 (1990)CrossRef

39.

Kanwal, S., Inam, S., Ali, R.., Qiu, S.: Two new variants of stickel’s key exchange protocol based on polynomials over noncommutative rings

40.

Janet, M.: Sur les systèmes d’équations aux dérivées partielles. J. Math. Pure et Appl. 3, 65–151 (1920)MATH

41.

Levy-dit-Vehel, F., Marinari, M.G., Perret, L., Traverso, C.: A Survey on Polly Cracker Systems in Sala, M., et al. (Ed.) Gröbner bases, Coding, Cryptography, Springer Risc XVI, pp. 285–305 (2009)

42.

Levy-dit-Vehel, F., Perret, L.: A Polly Cracker system based on satisfiability. Progress Comput. Sci. Appl. Logic 23, 177–192 (2004)MathSciNetMATH

43.

Macaulay, F.S.: On the resolution of a given modular system into primary systems including some properties of Hilbert Numbers. Math. Ann. 74, 66–121 (1913)MathSciNetCrossRef

44.

Macaulay, F.S.: The Algebraic Theory of Modular Systems. Cambridge Univ. Press, Cambridge (1916)MATH

45.

Madlener, K., Reinert, B.: Computing Gröbner bases in monoid and group rings, Proc. ISSAC ’93, ACM, pp. 254–263 (1993)

46.

Maza, G.: Algebraic Methods for Constructing One-Way Trapdoor Functions, PhD Thesis, University of Notre Dame, 2003. http://user.math.uzh.ch/maze/Articles/DissJoli.pdf

47.

Maza, G., Monico, C., Rosenthal, J.: Public Key Cryptography based on Semigroup Actions [pdf arXiv]. In Advances of Mathematics of Communications, Vol. 1, 4 (2007), pp. 489-507. https://www.math.uzh.ch/aa/fileadmin/user/rosen/publikation/ma07.pdf

48.

Mårtensson, K.: An algorithm to detect regular behaviour of binomial Gröbner Basis rational language. Master’s Thesis, Lund University (2006)

49.

Micciancio, D., Peikert, C.: Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. L.N.C.S 7237, 700–718 (2010)MathSciNetMATH

50.

Möller, H.M.: On the construction of Gröbner bases using syzygies. J. Symb. Comp. 6, 345–359 (1988)CrossRef

51.

Mora, F.: De Nugis Groebnerialium 2: Applying Macaulay’s Trick in order to easily write a Groebner basis. J. Appl. Alg.(2003)

52.

Nguefack, B., Pola, E.: Effective Buchberger-Zacharias-Weispfenning theory of skew polynomial extensions of restricted bilateral coherent rings. J. Symb. Comp. (2019). https://doi.org/10.1016/j.jsc.2019.03.003

53.

Mora, T.: Solving Polynomial Equation Systems 4 Vols., Cambridge University Press, I (2003), II (2005), III (2015), IV (2016)

54.

Mullan, C.: Some results in group-based cryptography, Technical report, Department of Mathematics, Royal Holloway, University of London (2012)

55.

Ore, O.: Theory of non-commutative polynomials. Ann. Math. 34, 480–508 (1933)MathSciNetCrossRef

56.

Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms, In Ueli M. Maurer, editor, Advances in Cryptology—EUROCRYPT’96, volume 1070 of Lecture Notes in Com-puter Science, pages 33–48. Springer (1996)

57.

Pesch, M.: Gröbner bases in skew polynomial rings. Dissertation, Passau (1997)

58.

Pritchard, F.L.: The ideal membership problem in non-commutative polynomial rings. J. Symb. Comp. 22, 27–48 (1996)MathSciNetCrossRef

59.

Rai, T.S.: Infinite Gröbner bases and Noncommutative Polly Cracker Cryptosystems PhD Thesis, Virginia Polytechnique Institute and State Univ. (2004)

60.

Rai, T.S.: Countering chosen-ciphertext attacks against noncommutative polly cracker cryptosystems (2005) Cryptology ePrint Archive: Report 2005/344. https://eprint.iacr.org/2005/344.pdf

61.

Reinert, B.: On Gröbner Bases in Monoid and Group Rings, Thesis. Kaiserslautern (1995)

62.

Shpilrain, V.: Cryptanalysis of Stickel’s key exchange scheme. Proc. Comput. Sci. Russia 5010, 283–288 (2008)MATH

63.

Shpilrain, V., Ushakov, A.: Thompson’s group and public key cryptography. In Third International Conference, ACNS 2005, volume 3531 of Lecture Notes in Comput. Sci., pages 151-163. Springer, Berlin, (2005). Availabe at https://arxiv.org/pdf/math/0505487v1.pdf

64.

Sramka, M.: On the security of stickel’s key exchange scheme. JCMCC 66 (2008)

65.

Stickel, E.: A new method for exchanging secret key, Proceedings of the Third International Conference on Information Technology and Applications (ICITA’05), 426–430. Sidney, Australia (2005)

66.

Steinwandt, R., Geiselmann, W., Endsuleit, R.: Attacking a polynomial-based cryptosystem: Polly Cracker. Int. J. Inf. Secur. 1, 143–148 (2002)CrossRef

67.

Steinwandt, R., Geiselmann, W.: Cryptoasnalysis of Polly Cracker. IEEE Trans. Inf. Th. 48(11), 2990–1 (2002)CrossRef

68.

Hofheinz, D., Steinwandt, R.: A “Differential” Attack on Polly Cracker. Int. J. Inf. Secur. 1, 143–148 (2002)CrossRef

69.

Wagner, N.R., Magyarik, M.R.: A Publyc-Key Cryptosystem based on the Word Problem. L. N. Comp. Sci 196, 19–36 (1985). SpringerMATH

70.

Wiesinger-Widi, M.: Groebner Bases and Generalized Sylvester Matrices. Ph.D. Thesis, Johannes Kepler University, Institute for Symbolic Computation, submitted (2014). https://www.dk-compmath.jku.at/publications/phd-theses/2015-06-05/view

Titel: Why you cannot even hope to use Gröbner bases in cryptography: an eternal golden braid of failures
verfasst von: Boo Barkee
Michela Ceria
Theo Moriarty
Andrea Visconti
Publikationsdatum: 17.04.2020
Verlag: Springer Berlin Heidelberg
Erschienen in: Applicable Algebra in Engineering, Communication and Computing / Ausgabe 3-4/2020
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-020-00428-w

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3-4/2020

Boomerang uniformity of normalized permutation polynomials of low degree

A trigonometric approach for Dickson polynomials over fields of characteristic two

HELP: a sparse error locator polynomial for BCH codes

A nonexistence certificate for projective planes of order ten with weight 15 codewords

Special Issue: “Computer Algebra and Application to Combinatorics, Coding Theory and Cryptography” ACA 2019, Montreal, Canada, July 16–20, 2019

Hamming distance of repeated-root constacyclic codes of length over