Don't Use It Twice: Reloaded! On the Lattice Isomorphism Group Action
Authors
Alessandro Budroni, Jesús-Javier Chi-Domínguez, Ermes Franch
Alessandro Budroni
Cryptography Research Center, Technology Innovation Institute, Abu Dhabi, UAE
alessandro dot budroni at tii dot ae
alessandro dot budroni at tii dot ae
Jesús-Javier Chi-Domínguez
Cryptography Research Center, Technology Innovation Institute, Abu Dhabi, UAE
jesus dot dominguez at tii dot ae
jesus dot dominguez at tii dot ae
Ermes Franch
University of Bergen, Bergen, Norway
ermes dot franch at uib dot no
ermes dot franch at uib dot no
Abstract
Group actions have emerged as a powerful framework in post-quantum cryptography, serving as the foundation for various cryptographic primitives. The Lattice Isomorphism Problem (LIP) has recently gained attention as a promising hardness assumption for designing quantum-resistant protocols. Its formulation as a group action has opened the door to new cryptographic applications, including a commitment scheme and a linkable ring signature.
In this work, we analyze the security properties of the LIP group action and present new findings. Specifically, we demonstrate that it fails to satisfy the weak unpredictability and weak pseudorandomness properties when the adversary has access to as few as three and two instances with the same secret, respectively. This significantly improves upon prior analysis by Budroni et al. (PQCrypto 2024).
As a direct consequence of our findings, we reveal a vulnerability in the linkable ring signature scheme proposed by Khuc et al. (SPACE 2024), demonstrating that the hardness assumption underlying the linkable anonymity property does not hold.
References
[BBCK24]
Benjamin Benčina, Alessandro Budroni, Jesús-Javier Chi-Domínguez, and Mukul Kulkarni. Properties of Lattice Isomorphism as a Cryptographic Group Action. In Markku-Juhani Saarinen and Daniel Smith-Tone, editors, Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Part I, pages 170–201, Oxford, UK. 2024. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-62743-9_6
[BBD+25]
Joppe W. Bos, Olivier Bronchain, Léo Ducas, Serge Fehr, Yu-Hsuan Huang, Thomas Pornin, Eamonn W. Postlethwaite, Thomas Prest, Ludo N. Pulles, and Wessel van Woerden. HAWK version 2.0 (March 2025). Tech. rep., National Institute of Standards and Technology. 2025.
[BBMP24]
Michele Battagliola, Giacomo Borin, Alessio Meneghetti, and Edoardo Persichetti. Cutting the GRASS: Threshold GRoup Action Signature Schemes. In Elisabeth Oswald, editor, CT-RSA 2024, volume 14643 of LNCS, pages 460–489, San Francisco, CA, USA. 2024. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-58868-6_18
[BCD+24]
Alessandro Budroni, Jesús-Javier Chi-Domínguez, Giuseppe D'Alconzo, Antonio J. Di Scala, and Mukul Kulkarni. Don't Use it Twice! Solving Relaxed Linear Equivalence Problems. In Kai-Min Chung and Yu Sasaki, editors, ASIACRYPT 2024, Part VIII, volume 15491 of LNCS, pages 35–65, Kolkata, India. 2024. Springer, Singapore, Singapore. DOI: 10.1007/978-981-96-0944-4_2
[BCDF25]
Alessandro Budroni, Jesús-Javier Chi-Domínguez, and Ermes Franch. Available at https://github.com/Crypto-TII/pqc-duit-reloaded. 2025.
[BGPS23]
Huck Bennett, Atul Ganju, Pura Peetathawatchai, and Noah Stephens-Davidowitz. Just How Hard Are Rotations of $\mathbb{{Z}}^n$? Algorithms and Cryptography with the Simplest Lattice. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part V, volume 14008 of LNCS, pages 252–281, Lyon, France. 2023. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-30589-4_9
[BKP20]
Ward Beullens, Shuichi Katsumata, and Federico Pintore. Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part II, volume 12492 of LNCS, pages 464–492, Daejeon, South Korea. 2020. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-64834-3_16
[BM21]
Tamar Lichter Blanks and Stephen D. Miller. Generating Cryptographically-Strong Random Lattice Bases and Recognizing Rotations of $\mathbb {{Z}}^n$. In Jung Hee Cheon and Jean-Pierre Tillich, editors, Post-Quantum Cryptography - 12th International Workshop, PQCrypto 2021, pages 319–338, Daejeon, South Korea. 2021. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-81293-5_17
[BMPS20]
Jean-François Biasse, Giacomo Micheli, Edoardo Persichetti, and Paolo Santini. LESS is More: Code-Based Signatures Without Syndromes. In Abderrahmane Nitaj and Amr M. Youssef, editors, AFRICACRYPT 20, volume 12174 of LNCS, pages 45–65, Cairo, Egypt. 2020. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-51938-4_3
[BY91]
Gilles Brassard and Moti Yung. One-Way Group Actions. In Alfred J. Menezes and Scott A. Vanstone, editors, CRYPTO'90, volume 537 of LNCS, pages 94–107, Santa Barbara, CA, USA. 1991. Springer Berlin Heidelberg, Germany. DOI: 10.1007/3-540-38424-3_7
[CLM+18]
Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes. CSIDH: An Efficient Post-Quantum Commutative Group Action. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part III, volume 11274 of LNCS, pages 395–427, Brisbane, Queensland, Australia. 2018. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-03332-3_15
[CNP+23]
Tung Chou, Ruben Niederhagen, Edoardo Persichetti, Tovohery Hajatiana Randrianarisoa, Krijn Reijnders, Simona Samardjiska, and Monika Trimoska. Take Your MEDS: Digital Signatures from Matrix Code Equivalence. In Nadia El Mrabet, Luca De Feo, and Sylvain Duquesne, editors, AFRICACRYPT 23, volume 14064 of LNCS, pages 28–52, Sousse, Tunisia. 2023. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-37679-5_2
[DKQ+25]
Dung Hoang Duong, Xuan Thanh Khuc, Youming Qiao, Willy Susilo, and Chuanqi Zhang. Blind Signatures from Cryptographic Group Actions. Cryptology ePrint Archive, Paper 2025/397. 2025.
[DPPvW22]
Léo Ducas, Eamonn W. Postlethwaite, Ludo N. Pulles, and Wessel P. J. van Woerden. Hawk: Module LIP Makes Lattice Signatures Fast, Compact and Simple. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part IV, volume 13794 of LNCS, pages 65–94, Taipei, Taiwan. 2022. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-22972-5_3
[DvW22]
Léo Ducas and Wessel P. J. van Woerden. On the Lattice Isomorphism Problem, Quadratic Forms, Remarkable Lattices, and Cryptography. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part III, volume 13277 of LNCS, pages 643–673, Trondheim, Norway. 2022. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-07082-2_23
[HJ94]
Roger A. Horn and Charles R. Johnson. Topics in Matrix Analysis. Cambridge University Press, Cambridge; New York 1994.
[JWL+25]
Kaijie Jiang, Anyu Wang, Hengyi Luo, Guoxiao Liu, Gang Tang, Yanbin Pan, and Xiaoyun Wang. Re-randomize and Extract: A Novel Commitment Construction Framework Based on Group Actions. In Advances in Cryptology - EUROCRYPT 2025: 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings, Part VII, pages 124–153, Cham. 2025. Springer Nature Switzerland. DOI: 10.1007/978-3-031-91124-8_5
[KTS+24]
Xuan Thanh Khuc, Anh The Ta, Willy Susilo, Dung Hoang Duong, Fuchun Guo, Kazuhide Fukushima, and Shinsaku Kiyomoto. Logarithmic-Size (Linkable) Ring Signatures from Lattice Isomorphism Problems. In Francesco Regazzoni, Bodhisatwa Mazumdar, and Sri Parameswaran, editors, Security, Privacy, and Applied Cryptography Engineering, pages 214–241, Cham. 2024. Springer Nature Switzerland. DOI: https://doi.org/10.1007/978-3-031-51583-5_13
[Lai24]
Yi-Fu Lai. Capybara and Tsubaki: Verifiable Random Functions from Group Actions and Isogenies. IACR Communications in Cryptology, 1(3), 2024. DOI: 10.62056/avr-11zn4
[LR24]
Antonin Leroux and Maxime Roméas. Updatable Encryption from Group Actions. In Markku-Juhani Saarinen and Daniel Smith-Tone, editors, Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Part II, pages 20–53, Oxford, UK. 2024. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-62746-0_2
[MG02]
Daniele Micciancio and Shafi Goldwasser. Complexity of Lattice Problems: A Cryptographic Perspective, volume 671. Springer Science+Business Media, LLC 2002. DOI: 10.1007/978-1-4615-0897-7
[{Nat}17]
National Institute of Standards and Technology. Post-Quantum Cryptography Standardization. https://csrc.nist.gov/projects/post-quantum-cryptography. 2017.
[TDJ+22]
Gang Tang, Dung Hoang Duong, Antoine Joux, Thomas Plantard, Youming Qiao, and Willy Susilo. Practical Post-Quantum Signature Schemes from Isomorphism Problems of Trilinear Forms. In Advances in Cryptology – EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 – June 3, 2022, Proceedings, Part III, pages 582–612, Berlin, Heidelberg. 2022. Springer-Verlag. DOI: 10.1007/978-3-031-07082-2_21
[{The}22]
The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.5). , 2022.
PDF
History
Submitted: 2025-03-19
Accepted: 2025-06-02
Published: 2025-07-07
Accepted: 2025-06-02
Published: 2025-07-07
How to cite
Alessandro Budroni, Jesús-Javier Chi-Domínguez, and Ermes Franch, Don't Use It Twice: Reloaded! On the Lattice Isomorphism Group Action. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/ay76chdj.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.