SpringerLink
Log in

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

  • Original Paper
  • Published:
Applicable Algebra in Engineering, Communication and Computing Aims and scope

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 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}$$

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

  3. 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)\).

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

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

  6. 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\).

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

References

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

    MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

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

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

    Article  Google Scholar 

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

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

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

    Article  Google Scholar 

  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  Google Scholar 

  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. ar**v:abs/cs/0508015

  14. Burger, R., Heinle, A.: A Diffie-Hellman-like key exchange protocol based on multivariate Ore polynomials. preprint (2014). ar**v: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)

    Article  Google Scholar 

  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). ar**v:1002.3180

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

    Article  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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)

    Article  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  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äuser

    MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  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  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  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 ar**v]. 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)

    MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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  Google Scholar 

  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)

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    MATH  Google Scholar 

  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

Download references

Author information

Authors and Affiliations

  1. Sore Bone, Milan, Italy

    Boo Barkee

  2. Department of Computer Science, University of Milan, Via Celoria 18, 20133, Milan, Italy

    Michela Ceria & Andrea Visconti

  3. SPECTRE, Milan, Italy

    Theo Moriarty

Authors
  1. Boo Barkee
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michela Ceria
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Theo Moriarty
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Andrea Visconti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michela Ceria.

Additional information

The second author has been partially funded by GNSAGA-Istituto Nazionale di Alta Matematica “Francesco Severi”, therefore she is thankful to this institution for its support.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Barkee, B., Ceria, M., Moriarty, T. et al. Why you cannot even hope to use Gröbner bases in cryptography: an eternal golden braid of failures. AAECC 31, 235–252 (2020). https://doi.org/10.1007/s00200-020-00428-w

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00200-020-00428-w

Keywords

Search

Navigation