[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Properties of Lattice Isomorphism as a Cryptographic Group Action

  • Conference paper
  • First Online:
Post-Quantum Cryptography (PQCrypto 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14771))

Included in the following conference series:

  • 382 Accesses

Abstract

In recent years, the Lattice Isomorphism Problem (LIP) has served as an underlying assumption to construct quantum-resistant cryptographic primitives, e.g. the zero-knowledge proof and digital signature scheme by Ducas and van Woerden (Eurocrypt 2022), and the HAWK digital signature scheme (Asiacrypt 2022).

While prior lines of work in group action cryptography, e.g. the works of Brassard and Yung (Crypto 1990), and more recently Alamati, De Feo, Montgomery and Patranabis (Asiacrypt 2020), focused on studying the discrete logarithm problem and isogeny-based problems in the group action framework, in recent years this framing has been used for studying the cryptographic properties of computational problems based on the difficulty of determining equivalence between algebraic objects. Examples include Permutation and Linear Code Equivalence Problems used in LESS (Africacrypt 2020), and the Tensor Isomorphism Problem (TCC 2019). This study delves into the quadratic form version of LIP, examining it through the lens of group actions.

In this work we (1) give formal definitions and study the cryptographic properties of this group action (LIGA), (2) demonstrate that LIGA lacks both weak unpredictability and weak pseudorandomness, and (3) under certain assumptions, establish a theoretical trade-off between time complexity and the required number of samples for breaking weak unpredictability, for large dimensions. We also conduct experiments supporting our analysis. Additionally, we employ our findings to formulate new hard problems on quadratic forms.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.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

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 89.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 64.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    This is in contrast to most of the prior works which consider group actions related to finite groups and/or sets. In [32] the authors mentioned that their definitions can be used in the setting of infinite groups and sets, specifically aiming at \(\textsf{LIP}\). However, they do not present \(\textsf{LIP}\) in the quadratic form setting and only consider the finite groups and sets for their analysis.

  2. 2.

    The Strassen’s algorithm is considered to be the best algorithm for large dimensional matrix multiplications with a running time of \(O\left( n^{\log _2(7)}\right) \) operations.

  3. 3.

    This fine-grained notion of limiting the number of times the adversary calls the oracle makes our results stronger since any attacker breaking the fine-grained security property also breaks the same property in the sense of [1, Sect. 2.1] (or other prior definitions of cryptographic properties of group actions.).

  4. 4.

    As the players are PPT, we may model the “random” permutation as a random oracle that uses \(\mathcal {D}_X\) to sample new images adaptively.

  5. 5.

    Notice that \(\textsf{LIGA}\), equipped with \(\mathcal {D}_s([Q])\) and an efficient sampler over \({{\text {GL}}}_n(\mathbb {Z})\) (Algorithm 1 or Extract in [25]), follows the definition of an Effective Group Action from [1], with the relaxation that the base set and group are infinite.

  6. 6.

    We have \(\widetilde{O}(\cdot )\) instead of \(O(\cdot )\) because of the increase of the integer coefficients size when applying this optimization trick.

References

  1. Alamati, N., De Feo, L., Montgomery, H., Patranabis, S.: Cryptographic group actions and applications. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 411–439. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-64834-3_14

  2. Apostol, T.M.: Calculus, Multi-variable Calculus and Linear Algebra, vol. II. Blaisdell, Waltham (1969)

    Google Scholar 

  3. Bardet, M.: Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. Ph.D. thesis, Université Pierre et Marie Curie - Paris VI (2004). https://theses.hal.science/tel-00449609

  4. Bardet, M., Faugère, J.C., Salvy, B.: Complexity of Gröbner basis computation for Semi-regular Overdetermined sequences over \(\mathbb{F}_2\) with solutions in \(\mathbb{F}_2\). Research Report RR-5049, INRIA (2003). https://inria.hal.science/inria-00071534

  5. Bardet, M., Faugère, J.C., Salvy, B.: On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations. In: Proceedings of the International Conference on Polynomial System Solving Paris, November 2004 in Honor of Daniel Lazard, pp. 71–75. ICPSS (2004)

    Google Scholar 

  6. Bardet, M., Faugère, J.C., Salvy, B., Yang, B.: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. In: 8th International Symposium on Effective Methods in Algebraic Geometry, pp. 1–17. MEGA (2005)

    Google Scholar 

  7. Bardet, M., Faugère, J.C., Salvy, B., Spaenlehauer, P.J.: On the complexity of solving quadratic Boolean systems. J. Complex. 29(1), 53–75 (2011). https://doi.org/10.1016/j.jco.2012.07.001

  8. Bennett, H., Ganju, A., Peetathawatchai, P., Stephens-Davidowitz, N.: Just how hard are rotations of \(\mathbb{Z}^{n}\)? algorithms and cryptography with the simplest lattice. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 252–281. Springer, Heidelberg (2023).https://doi.org/10.1007/978-3-031-30589-4_9

  9. Benčina, B., Budroni, A., Chi-Domínguez, J.J., Kulkarni, M.: lip-properties. https://github.com/JJChiDguez/lip-properties.git

  10. Berthomieu, J., Eder, C., Safey El Din, M.: msolve: a library for solving polynomial systems. In: Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation (ISSAC 2021), pp. 51–58. Association for Computing Machinery, Saint Petersburg (2021). https://doi.org/10.1145/3452143.3465545. Version 0.6.3

  11. Beullens, W., Kleinjung, T., Vercauteren, F.: CSI-FiSh: efficient isogeny based signatures through class group computations. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part I. LNCS, vol. 11921, pp. 227–247. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-34578-5_9

  12. Biasse, J.F., Micheli, G., Persichetti, E., Santini, P.: LESS is more: code-based signatures without syndromes. In: Nitaj, A., Youssef, A.M. (eds.) AFRICACRYPT 20. LNCS, vol. 12174, pp. 45–65. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-51938-4_3

  13. Blanks, T.L., Miller, S.D.: Generating cryptographically-strong random lattice bases and recognizing rotations of \(\mathbb{Z}^{n}\). In: Cheon, J.H., Tillich, J.P. (eds.) Post-Quantum Cryptography - 12th International Workshop, PQCrypto 2021, pp. 319–338. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-030-81293-5_17

  14. Bläser, M., et al.: On digital signatures based on isomorphism problems: orom security, ring signatures, and applications. Cryptology ePrint Archive, Paper 2022/1184 (2022). https://eprint.iacr.org/2022/1184

  15. Borin, G., Persichetti, E., Santini, P.: Zero-knowledge proofs from the action subgraph. Cryptology ePrint Archive, Paper 2023/718 (2023). https://eprint.iacr.org/2023/718

  16. Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC, pp. 575–584. ACM Press (2013). https://doi.org/10.1145/2488608.2488680

  17. Brassard, G., Yung, M.: One-way group actions. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO’90. LNCS, vol. 537, pp. 94–107. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_7

  18. Budroni, A., Chi-Domínguez, J.J., Kulkarni, M.: Lattice isomorphism as a group action and hard problems on quadratic forms. Cryptology ePrint Archive, Paper 2023/1093 - version 20230724:055703 (2023). https://eprint.iacr.org/archive/2023/1093/1690178223.pdf

  19. Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: an efficient post-quantum commutative group action. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part III. LNCS, vol. 11274, pp. 395–427. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-030-03332-3_15

  20. Couveignes, J.M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006). https://eprint.iacr.org/2006/291

  21. Cox, D.A., Little, J., O’Shea, D.: Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. In: Undergraduate Texts in Mathematics, 4th edn. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16721-3

  22. D’Alconzo, G., Scala, A.J.D.: Representations of group actions and their applications in cryptography. Cryptology ePrint Archive, Paper 2023/1247 (2023). https://eprint.iacr.org/2023/1247

  23. De Feo, L., et al.: SCALLOP: scaling the CSI-FiSh. In: Boldyreva, A., Kolesnikov, V. (eds.) PKC 2023, Part I. LNCS, vol. 13940, pp. 345–375. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-31368-4_13

  24. Ducas, L., Postlethwaite, E.W., Pulles, L.N., van Woerden, W.P.J.: Hawk: module LIP makes lattice signatures fast, compact and simple. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part IV. LNCS, vol. 13794, pp. 65–94. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22972-5_3

  25. Ducas, L., van Woerden, W.P.J.: On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography. In: Dunkelman and Dziembowski [26], pp. 643–646. https://doi.org/10.1007/978-3-031-07082-2_23

  26. Dunkelman, O., Dziembowski, S. (eds.): EUROCRYPT 2022, Part III, LNCS, vol. 13277. Springer, Heidelberg (2022)

    Google Scholar 

  27. Felderhoff, J.: Hard Homogenous Spaces and Commutative Supersingular Isogeny based Diffie-Hellman (2019). https://api.semanticscholar.org/CorpusID:252082464

  28. Fröberg, R.: An inequality for hilbert series of graded algebras. Math. Scand. 56(2), 117–144 (1985)

    Article  MathSciNet  Google Scholar 

  29. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 197–206. ACM Press (2008). https://doi.org/10.1145/1374376.1374407

  30. Gentry, C., Szydlo, M.: Cryptanalysis of the revised NTRU signature scheme. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 299–320. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_20

  31. Haviv, I., Regev, O.: On the lattice isomorphism problem. In: Chekuri, C. (ed.) 25th SODA, pp. 391–404. ACM-SIAM (2014). https://doi.org/10.1137/1.9781611973402.29

  32. Ji, Z., Qiao, Y., Song, F., Yun, A.: General linear group action on tensors: a candidate for post-quantum cryptography. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019, Part I. LNCS, vol. 11891, pp. 251–281. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-36030-6_11

  33. Joux, A.: MPC in the head for isomorphisms and group actions. Cryptology ePrint Archive, Paper 2023/664 (2023). https://eprint.iacr.org/2023/664

  34. Lazard, D.: Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In: van Hulzen, J.A. (ed.) Computer Algebra. LNCS, vol. 162, pp. 146–156. Springer, Heidelberg (1983). https://doi.org/10.1007/3-540-12868-9_99

  35. Machì, A.: Groups. Springer Milano (2012). https://doi.org/10.1007/978-88-470-2421-2

  36. Micciancio, D., Goldwasser, S.: Cryptographic functions. In: Micciancio, D., Goldwasser, S. (eds.) Complexity of Lattice Problems. LNCS, vol. 671, pp. 143–194. Springer, Boston (2002). https://doi.org/10.1007/978-1-4615-0897-7_8

  37. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007). https://doi.org/10.1137/s0097539705447360

    Article  MathSciNet  Google Scholar 

  38. Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: 38th FOCS, pp. 458–467. IEEE Computer Society Press (1997). https://doi.org/10.1109/SFCS.1997.646134

  39. NIST: Post-quantum cryptography: Digital signature schemes. https://csrc.nist.gov/projects/pqc-dig-sig

  40. NIST: Post-quantum cryptography standardization. https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022

  41. Rasslan, M.M.N., Youssef, A.M.: Cryptanalysis of a Public Key Encryption Scheme Using Ergodic Matrices. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 94-A(2), 853–854 (2011).https://doi.org/10.1587/transfun.E94.A.853

  42. Serre, J.P.: A Course in Arithmetic, Graduate Texts in Mathematics, vol. 7. Springer, New York (1973). https://doi.org/10.1007/978-1-4684-9884-4

  43. Spaenlehauer, J.P.: Résolution de Systèmes Multi-homogènes et Déterminantiels. Ph.D. thesis, Université Pierre et Marie Curie (2012)

    Google Scholar 

  44. Tang, G., Duong, D.H., Joux, A., Plantard, T., Qiao, Y., Susilo, W.: Practical post-quantum signature schemes from isomorphism problems of trilinear forms. In: Dunkelman and Dziembowski [26], pp. 582–612.https://doi.org/10.1007/978-3-031-07082-2_21

  45. The Sage Developers: SageMath, the Sage Mathematics Software System (Version 10.1) (2023). https://www.sagemath.org

Download references

Acknowledgments

The authors thank Keita Xagawa, Victor Mateu, and Martin R. Albrecht for fruitful discussions on the topic. We also thank Elena Kirshanova and anonymous reviewers for the useful comments on an earlier version of this manuscript. Benjamin Benčina was supported by the EPSRC and the UK Government as part of the grant EP/S021817/1.

Author information

Authors and Affiliations

  1. Royal Holloway, University of London, London, UK

    Benjamin Benčina

  2. Cryptography Research Center, Technology Innovation Institute, Abu Dhabi, UAE

    Alessandro Budroni, Jesús-Javier Chi-Domínguez & Mukul Kulkarni

Authors
  1. Benjamin Benčina
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alessandro Budroni
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jesús-Javier Chi-Domínguez
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mukul Kulkarni
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Benjamin Benčina .

Editor information

Editors and Affiliations

  1. Tampere University, Tampere, Finland

    Markku-Juhani Saarinen

  2. University of Louisville, Gaithersburg, MD, USA

    Daniel Smith-Tone

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Benčina, B., Budroni, A., Chi-Domínguez, JJ., Kulkarni, M. (2024). Properties of Lattice Isomorphism as a Cryptographic Group Action. In: Saarinen, MJ., Smith-Tone, D. (eds) Post-Quantum Cryptography. PQCrypto 2024. Lecture Notes in Computer Science, vol 14771. Springer, Cham. https://doi.org/10.1007/978-3-031-62743-9_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-62743-9_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-62742-2

  • Online ISBN: 978-3-031-62743-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation