Paper 2023/1093

Properties of Lattice Isomorphism as a Cryptographic Group Action

Benjamin Benčina, Royal Holloway University of London
Alessandro Budroni, Technology Innovation Institute
Jesús-Javier Chi-Domínguez, Technology Innovation Institute
Mukul Kulkarni, Technology Innovation Institute

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.

Available format(s)
Publication info
Published elsewhere. PQCrypto 2024
Gröbner BasesGroup ActionsLattice-based CryptographyLattice Isomorphism ProblemQuadratic Forms
Contact author(s)
benjamin bencina 2022 @ live rhul ac uk
budroni alessandro @ gmail com
jesus dominguez @ tii ae
mukul kulkarni @ tii ae
2024-04-26: last of 4 revisions
2023-07-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benjamin Benčina and Alessandro Budroni and Jesús-Javier Chi-Domínguez and Mukul Kulkarni},
      title = {Properties of Lattice Isomorphism as a Cryptographic Group Action},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1093},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.