Paper 2025/516

Don't Use It Twice: Reloaded! On the Lattice Isomorphism Group Action

Alessandro Budroni, Technology Innovation Institute
Jesús-Javier Chi-Domínguez, Technology Innovation Institute
Ermes Franch, University of Bergen
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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
lattice isomorphismgroup actionlinkable ring signaturecryptanalysispost-quantum cryptography
Contact author(s)
budroni alessandro @ gmail com
jesus dominguez @ tii ae
ermes franch @ uib no
History
2025-03-21: revised
2025-03-19: received
See all versions
Short URL
https://ia.cr/2025/516
License
Creative Commons Attribution-NonCommercial-ShareAlike
CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2025/516,
      author = {Alessandro Budroni and Jesús-Javier Chi-Domínguez and Ermes Franch},
      title = {Don't Use It Twice: Reloaded! On the Lattice Isomorphism Group Action},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/516},
      year = {2025},
      url = {https://eprint.iacr.org/2025/516}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.