Remote Access St. Petersburg Mathematical Journal

St. Petersburg Mathematical Journal

ISSN 1547-7371(online) ISSN 1061-0022(print)



Algebraic cryptography: New constructions and their security against provable break

Authors: D. Grigoriev, A. Kojevnikov and S. J. Nikolenko
Translated by: the authors
Original publication: Algebra i Analiz, tom 20 (2008), nomer 6.
Journal: St. Petersburg Math. J. 20 (2009), 937-953
MSC (2000): Primary 94A60, 68P25, 11T71
Published electronically: October 1, 2009
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Very few known cryptographic primitives are based on noncommutative algebra. Each new scheme is of substantial interest, because noncommutative constructions are secure against many standard cryptographic attacks. On the other hand, cryptography does not provide security proofs that might allow the security of a cryptographic primitive to rely upon structural complexity assumptions. Thus, it is important to investigate weaker notions of security.

In this paper, new constructions of cryptographic primitives based on group invariants are proposed, together with new ways to strengthen them for practical use. Also, the notion of a provable break is introduced, which is a weaker version of the regular cryptographic break. In this new version, an adversary should have a proof that he has correctly decyphered the message. It is proved that the cryptosystems based on matrix group invariants and a version of the Anshel-Anshel-Goldfeld key agreement protocol for modular groups are secure against provable break unless $ \mathrm{NP}=\mathrm{RP}$.

References [Enhancements On Off] (What's this?)

  • 1. M. Ajtai and C. Dwork, A public-key cryptosystem with worst-case/average-case equivalence, STOC'97: $ 29$th Annual ACM Symposium on Theory of Computing (El Paso, TX, 1997), ACM, New York, 1999, pp. 284-293 (electronic). MR 1715640
  • 2. I. Anshel, M. Anshel, B. Fisher, and D. Goldfeld, New key agreement protocols in braid group cryptography, Topics in Cryptology -- CT-RSA $ 2001$ (San Francisco, CA), Lecture Notes in Comput. Sci., vol. 2020, Springer, Berlin, 2001, pp. 13-27. MR 1907085 (2003c:94016)
  • 3. I. Anshel, M. Anshel, and D. Goldfeld, An algebraic method for public-key cryptography, Math. Res. Lett. 6 (1999), 287-291. MR 1713130 (2000e:94034)
  • 4. -, Non-abelian key agreement protocols, Discrete Appl. Math. 130 (2003), no. 1, 3-12. MR 2008401 (2004h:94050)
  • 5. M. Anshel, Braid group cryptography and quantum cryptoanalysis, $ 8$th Internat. Wigner Symposium (New York, U.S.A., 2003), Baruch College of CUNY, pp. 13-27.
  • 6. T. M. Apostol, Modular functions and Dirichlet series in number theory, Grad. Texts in Math., vol. 41, Springer, New York, 1990. MR 1027834 (90j:11001)
  • 7. S. Arora and B. Barak, Complexity theory: a modern approach,, 2008.
  • 8. J. Benaloh, Dense probabilistic encryption, $ 1$st Annual Workshop on Selected Areas in Cryptology (Queen's Univ., Kingston, Canada, 1994), Springer-Verlag, London, 1994, pp. 120-128.
  • 9. C. H. Bennett and P. W. Shor, Quantum information theory, Information Theory: 1948-1998, IEEE Trans. Inform. Theory 44 (1998), no. 6, 2724-2742. MR 1658902 (99h:94025)
  • 10. I. Blake, G. Seroussi, and N. Smart, Elliptic curves in cryptography, London Math. Soc. Lecture Note Ser., vol. 265, Cambridge Univ. Press, Cambridge, 2000. MR 1771549 (2001i:94048)
  • 11. A. Blass and Y. Gurevich, Matrix transformation is complete for the average case, SIAM J. Comput. 24 (1995), 3-29. MR 1313476 (96f:68037)
  • 12. N. Blum, A Boolean function requiring $ 3n$ network size, Theoret. Comput. Sci. 28 (1984), 337-345. MR 0742295 (86g:68053)
  • 13. A. Bogdanov and L. Trevisan, On worst-case to average-case reductions for NP problems, $ 44$th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03) (Cambridge, MA, U.S.A., 2003), IEEE Computer Soc., Washington, DC, 2003, pp. 308-317.
  • 14. D. Boneh and R. Venkatesan, Breaking RSA may not be equivalent to factoring, Advances in Cryptology -- EUROCPYPT'98 (Espoo), Lecture Notes in Comput. Sci., vol. 1403, Springer, Berlin, 1998, pp. 59-71. MR 1729052
  • 15. D. R. L. Brown, Breaking RSA may be as difficult as factoring, Tech. Rep. 2005/380, Cryptology ePrint Archive, 2005.
  • 16. W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), 644-654. MR 0437208 (55:10141)
  • 17. C. Dwork, Positive applications of lattices to cryptography, Mathematical Foundations of Computer Science 1997 (Bratislava) (MFCS'97), Lecture Notes in Comput. Sci., vol. 1295, Springer, Berlin, 1997, pp. 44-51. MR 1640207 (99k:94034)
  • 18. S. Even and Y. Yacobi, Cryptocomplexity and NP-completeness, Automata, Languages and Programming (Proc. Seventh Internat. Colloq., Noordwijkerhout, 1980), Lecture Notes in Comput. Sci., vol. 85, Springer, Berlin-New York, 1980, pp. 195-207. MR 0589004 (82a:94085)
  • 19. J. Feigenbaum and M. Merritt, Open questions, talk abstracts, and summary of discussions, Distributed Computing and Cryptography (Princeton, NJ, 1989), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 2, Amer. Math. Soc., Providence, RI, 1991, pp. 1-45. MR 1105537 (92b:68006)
  • 20. M. Fellows and N. Koblitz, Combinatorial cryptosystems galore! Finite Fields: Theory, Applications, and Algorithms (Las Vegas, NV, 1993), Contemp. Math., vol. 168, Amer. Math. Soc., Providence, RI, 1994, pp. 51-61. MR 1291417 (95e:94028)
  • 21. O. Goldreich, Introduction to complexity theory, Lecture notes, Weizmann Inst. Sci., 1998-1999.
  • 22. S. Goldwasser and M. Bellare, Lecture notes on cryptography, Summer course on cryptography at MIT, 2001.
  • 23. S. Goldwasser and S. Micali, Probabilistic encryption, J. Comput. System Sci. 28 (1984), 270-299. MR 0760548 (86j:94047)
  • 24. D. Grigoriev, Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines, Theoret. Comput. Sci. 180 (1997), 217-228. MR 1453867 (98b:68090)
  • 25. -, Public-key cryptography and invariant theory, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 293 (2002), 26-38; English transl., J. Math. Sci. (N. Y.) 126 (2005), no. 3, 1152-1157. MR 1948823 (2003m:94065)
  • 26. D. Grigoriev, E. A. Hirsch, and K. Pervyshev, A complete public-key cryptosystem, Groups, Complexity, Cryptology 1 (2009), 1-12. MR 2502933
  • 27. D. Grigoriev, A. Kojevnikov, and S. I. Nikolenko, Invariant-based cryptosystems and their security against provable break, Tech. Rep. 158, Max-Planck-Inst. Preprints, 2007.
  • 28. D. Grigoriev and I. Ponomarenko, Homomorphic public-key cryptosystems over groups and rings, Complexity of Computations and Proofs, Quad. Mat., No. 13, Dept. Math. Seconda Univ. Napoli, Caserta, 2004, pp. 305-325. MR 2131411 (2006b:94027)
  • 29. -, On non-abelian homomorphic public-key cryptosystems, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 293 (2002), 39-58; English transl., J. Math. Sci. (N. Y.) 126 (2005), no. 3, 1158-1166. MR 1948824 (2004a:94044)
  • 30. -, Homomorphic public-key cryptosystems and encrypting Boolean circuits, Appl. Algebra Engrg. Comm. Comput. 17 (2006), 239-255. MR 2233784 (2008b:94067)
  • 31. -, Constructions in public-key cryptography over matrix groups, Algebraic Methods in Cryptography (L. Gerritzen, D. Goldfeld, M. Kreuzer, R. Gerhard, and V. Shpilrain, eds.), Contemp. Math., vol. 418, Amer. Math. Soc., Providence, RI, 2006, pp. 103-119. MR 2389292
  • 32. D. Hankerson, A. Menezes, and S. Vanstone, Guide to elliptic curve cryptography, Springer-Verlag, New York, 2004. MR 2054891 (2005c:94049)
  • 33. D. Harnik, J. Kilian, M. Naor, O. Reingold, and A. Rosen, On robust combiners for oblivious transfer and other primitives, Advances in Cryptology -- EUROCRYPT 2005, Lecture Notes in Comput. Sci., vol. 3494, Springer, Berlin, 2005, pp. 96-113. MR 2352183 (2008i:94043)
  • 34. A. P. Hiltgen, Constructions of feebly-one-way families of permutations, Advances in Cryptology -- AUSCRYPT'92 (Gold Coast, 1992), Lecture Notes in Comput. Sci., vol. 718, Springer, Berlin, 1993, pp. 422-434. MR 1292706 (96e:94014)
  • 35. -, Towards a better understanding of one-wayness: Facing linear permutations, Advances in Cryptology -- EUROCRYPT'98 (Espoo), Lecture Notes in Comput. Sci., vol. 1403, Springer, Berlin, 1998, pp. 319-333. MR 1729060 (2000i:94050)
  • 36. E. A. Hirsch and S. I. Nikolenko, A feebly trapdoor function, PDMI Preprints no. 16/2008, S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), St. Petersburg, 2008.
  • 37. N. Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), 203-209. MR 0866109 (88b:94017)
  • 38. A. Kojevnikov and S. I. Nikolenko, New combinatorial complete one-way functions, $ 25^{\text{th}}$ Symposium on Theoretical Aspects of Computer Science (STACS'08) (Bordeaux, February 2008), Bordeaux, 2008.
  • 39. A. Lempel, Cryptography in transition, Comput. Surveys 11 (1979), no. 4, 215-220.
  • 40. L. A. Levin, One-way functions and pseudorandom generators, Combinatorica 7 (1987), 357-363. MR 0931193 (89c:68048)
  • 41. -, One-way functions, Problemy Peredachi Inf. 39 (2003), no. 1, 103-117; English transl., Probl. Inf. Transm. 39 (2003), no. 1, 92-103. MR 2101668 (2005g:94080)
  • 42. H.-K. Lo, T. Spiller, and S. Popescu (eds.), Introduction to quantum computation and information, World Sci. Publ. Co., Inc., River Edge, NJ, 1998. MR 1750536 (2000k:81058)
  • 43. E. M. Luks, Permutation groups and polynomial-time computation, Groups and Computation (New Brunswick, NJ, 1991), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, Amer. Math. Soc., Providence, RI, 1993, pp. 139-175. MR 1235801 (94h:20005)
  • 44. L. V. Ly, Polly Two: A new algebraic polynomial-based public-key scheme, Appl. Algebra Engrg. Comm. Comput. 17 (2006), 267-283. MR 2233786 (2007c:94149)
  • 45. V. S. Miller, Use of elliptic curves in cryptography, Advances in Cryptology -- CRYPTO'85 (Santa Barbara, CA, 1985), Lecture Notes in Comput. Sci., vol. 218, Springer, Berlin, 1986, pp. 417-426. MR 0851432 (88b:68040)
  • 46. A. G. Myasnikov, V. Shpilrain, and A. Ushakov, Group-based cryptography, Birkhäuser, Basel, 2008. MR 2437984 (2009d:94098)
  • 47. D. Naccache and J. Stern, A new public-key cryptosystem based on higher residues, $ 5$th ACM Conference on Computer and Communication Security (San Francisco, CA, U.S.A., 1998), ACM Press, San Francisco, CA, 1998, pp. 59-66. MR 1603095
  • 48. M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge Univ. Press, Cambridge, 2000. MR 1796805 (2003j:81038)
  • 49. T. Okamoto and S. Uchiyama, A new public-key cryptosystem as secure as factoring, Advances in Cryptology -- EUROCRYPT'98 (Espoo), Lecture Notes in Comput. Sci., vol. 1403, Springer, Berlin, 1998, pp. 308-318. MR 1729059
  • 50. D. K. Rappe, Algebraisch homomorphe Kryptosysteme, Diplomarbeit, Dem Fachbereich Mathematik der Universitat Dortmund, 2000.
  • 51. O. Regev, On lattices, learning with errors, random linear codes, and cryptography, STOC'05: $ 37$th Annual ACM Symposium on Theory of Computing (Baltimore, MD, U.S.A., 2005), ACM, New York, 2005, pp. 84-93. MR 2181605 (2006g:94031)
  • 52. -, Lattice-based cryptography, $ 26$th Annual International Cryptology Conference (CRYPTO'06) (Santa Barbara, CA, U.S.A., 2006), Lecture Notes in Comput. Sci., vol. 4117, Springer, Berlin, 2006, pp. 131-141. MR 2422159
  • 53. R. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120-126. MR 0700103 (83m:94003)
  • 54. R. L. Rivest and B. Kaliski, RSA problem, Encyclopedia of Cryptography and Security, Kluwer Publ. House, 2005.
  • 55. P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26 (1997), no. 5, 1484-1509. MR 1471990 (98i:11108)
  • 56. L. Smith, Polynomial invariants of finite groups, Res. Notes Math., vol. 6, A. K. Peters, Wellesley, MA, 1995. MR 1328644 (96f:13008)
  • 57. R. Venkatesan and S. Rajagopalan, Average case intractability of matrix and diophantine problems, STOC'92: $ 24$th Annual ACM Symposium on Theory of Computing (Victoria, British Columbia, Canada, May 1992), ACM, New York, 1992, pp. 632-642.
  • 58. L. Washington, Elliptic curves. Number theory and cryptography, Chapman & Hall / CRC, Boca Raton, FL, 2003. MR 1989729 (2004e:11061)
  • 59. I. Wegener, The complexity of Boolean functions, John Wiley and Sons, Ltd., Chichester; B. G. Teubner, Stuttgart, 1987. MR 0905473 (89b:03066)
  • 60. A. Yao, How to generate and exchange secrets, $ 27$th IEEE Symposium on the Foundations of Computer Science (FOCS'$ 86$) (Toronto, Canada, October 1986), IEEE Computer Society, 1986, pp. 162-187.

Similar Articles

Retrieve articles in St. Petersburg Mathematical Journal with MSC (2000): 94A60, 68P25, 11T71

Retrieve articles in all journals with MSC (2000): 94A60, 68P25, 11T71

Additional Information

D. Grigoriev
Affiliation: CNRS, Laboratoire des Mathématiques, Université de Lille, 59655 Villeneuve d’Ascq, France

A. Kojevnikov
Affiliation: St. Petersburg Branch, Steklov Mathematical Institute, Russian Academy of Sciences, Fontanka 27, 191023 St. Petersburg, Russia

S. J. Nikolenko
Affiliation: St. Petersburg Branch, Steklov Mathematical Institute, Russian Academy of Sciences, Fontanka 27, 191023 St. Petersburg, Russia

Keywords: Algebraic cryptography, cryptographic primitives, provable break
Received by editor(s): January 9, 2008
Published electronically: October 1, 2009
Additional Notes: The research was done during the stay at the Max-Planck-Institut für Mathematik, Bonn, Germany.
The second and third authors were supported in part by INTAS (YSF fellowship no. 05-109-5565) and by RFBR (grant nos. 05-01-00932 and 06-01-00502).
Article copyright: © Copyright 2009 American Mathematical Society

American Mathematical Society