{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:40:06Z","timestamp":1751924406588,"version":"3.41.2"},"reference-count":24,"publisher":"International Association for Cryptologic Research","issue":"2","license":[{"start":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T00:00:00Z","timestamp":1742342400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,6,2]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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).<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.62056\/ay76chdj","type":"journal-article","created":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:09:09Z","timestamp":1751922549000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Don't Use It Twice: Reloaded! On the Lattice Isomorphism Group Action"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3544-5128","authenticated-orcid":false,"given":"Alessandro","family":"Budroni","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/001kv2y39","id-type":"ROR","asserted-by":"publisher"}],"name":"Cryptography Research Center, Technology Innovation Institute","place":["Abu Dhabi, UAE"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9753-7263","authenticated-orcid":false,"given":"Jes\u00fas-Javier","family":"Chi-Dom\u00ednguez","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/001kv2y39","id-type":"ROR","asserted-by":"publisher"}],"name":"Cryptography Research Center, Technology Innovation Institute","place":["Abu Dhabi, UAE"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-7372-1444","authenticated-orcid":false,"given":"Ermes","family":"Franch","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03zga2b32","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Bergen","place":["Bergen, Norway"]}]}],"member":"48349","published-online":{"date-parts":[[2025,7,7]]},"reference":[{"key":"ref1:NIST:competition","volume-title":"Post-Quantum Cryptography Standardization","author":"National Institute of Standards","year":"2017"},{"key":"ref2:C:BraYun90","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/3-540-38424-3_7","article-title":"One-Way Group Actions","volume":"537","author":"Gilles Brassard","year":"1991"},{"key":"ref3:AC:BeuKatPin20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/978-3-030-64834-3_16","article-title":"Calamari and Falafl: Logarithmic (Linkable) Ring\n  Signatures from Isogenies and Lattices","volume":"12492","author":"Ward Beullens","year":"2020"},{"key":"ref4:RSA:BBMP24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/978-3-031-58868-6_18","article-title":"Cutting the GRASS: Threshold GRoup Action Signature\n  Schemes","volume":"14643","author":"Michele Battagliola","year":"2024"},{"key":"ref5:cryptoeprint:2025\/397","volume-title":"Blind Signatures from Cryptographic Group Actions","author":"Dung Hoang Duong","year":"2025"},{"key":"ref6:CiC-1-3-1","doi-asserted-by":"publisher","DOI":"10.62056\/avr-11zn4","article-title":"Capybara and Tsubaki: Verifiable Random Functions from Group\n  Actions and Isogenies","volume":"1","author":"Yi-Fu Lai","year":"2024","journal-title":"IACR Communications in Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/3006-5496","issn-type":"electronic"},{"key":"ref7:cryptoeprint:2025\/400","isbn-type":"print","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-031-91124-8_5","article-title":"Re-randomize and Extract: A Novel Commitment Construction\n  Framework Based on Group Actions","author":"Kaijie Jiang","year":"2025","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031911248"},{"key":"ref8:PQCRYPTO:LerRom24","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/978-3-031-62746-0_2","article-title":"Updatable Encryption from Group Actions","author":"Antonin Leroux","year":"2024"},{"key":"ref9:AC:CLMPR18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-030-03332-3_15","article-title":"CSIDH: An Efficient Post-Quantum Commutative Group\n  Action","volume":"11274","author":"Wouter Castryck","year":"2018"},{"key":"ref10:PQCRYPTO:BBCK24","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-031-62743-9_6","article-title":"Properties of Lattice Isomorphism as a Cryptographic Group\n  Action","author":"Benjamin Ben\u010dina","year":"2024"},{"key":"ref11:AFRICACRYPT:BMPS20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-030-51938-4_3","article-title":"LESS is More: Code-Based Signatures Without Syndromes","volume":"12174","author":"Jean-Fran\u00e7ois Biasse","year":"2020"},{"key":"ref12:AFRICACRYPT:CNPRRS23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-031-37679-5_2","article-title":"Take Your MEDS: Digital Signatures from Matrix Code\n  Equivalence","volume":"14064","author":"Tung Chou","year":"2023"},{"key":"ref13:ALTEQ","isbn-type":"print","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1007\/978-3-031-07082-2_21","article-title":"Practical Post-Quantum Signature Schemes from Isomorphism\n  Problems of Trilinear Forms","author":"Gang Tang","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031070815"},{"key":"ref14:EC:DucvWo22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-031-07082-2_23","article-title":"On the Lattice Isomorphism Problem, Quadratic Forms,\n  Remarkable Lattices, and Cryptography","volume":"13277","author":"L\u00e9o Ducas","year":"2022"},{"key":"ref15:EC:BGPS23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-031-30589-4_9","article-title":"Just How Hard Are Rotations of $\\mathbb{{Z}}^n$? Algorithms\n  and Cryptography with the Simplest Lattice","volume":"14008","author":"Huck Bennett","year":"2023"},{"key":"ref16:AC:DPPW22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-031-22972-5_3","article-title":"Hawk: Module LIP Makes Lattice Signatures Fast, Compact\n  and Simple","volume":"13794","author":"L\u00e9o Ducas","year":"2022"},{"key":"ref17:HawkNIST","volume-title":"HAWK version 2.0 (March 2025)","author":"Joppe W. Bos","year":"2025"},{"key":"ref18:SPACE:KTSDGFK24","isbn-type":"print","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-031-51583-5_13","article-title":"Logarithmic-Size (Linkable) Ring Signatures from\u00a0Lattice\n  Isomorphism Problems","author":"Xuan Thanh Khuc","year":"2024","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031515835"},{"key":"ref19:AC:BCDSK24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-981-96-0944-4_2","article-title":"Don't Use it Twice! Solving Relaxed Linear Equivalence\n  Problems","volume":"15491","author":"Alessandro Budroni","year":"2024"},{"key":"ref20:sagemath","volume-title":"SageMath, the Sage Mathematics Software System\n  (Version 9.5)","author":"The Sage Developers","year":"2022"},{"key":"ref21:public_repo","author":"Alessandro Budroni","year":"2025"},{"key":"ref22:PQCRYPTO:BlaMil21","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-030-81293-5_17","article-title":"Generating Cryptographically-Strong Random Lattice Bases and\n  Recognizing Rotations of $\\mathbb {{Z}}^n$","author":"Tamar Lichter Blanks","year":"2021"},{"key":"ref23:book:MG02","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0897-7","volume-title":"Complexity of Lattice Problems: A Cryptographic\n  Perspective","volume":"671","author":"Daniele Micciancio","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/9781461352938"},{"key":"ref24:horn94","isbn-type":"print","volume-title":"Topics in Matrix Analysis","author":"Roger A. Horn","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0521467136"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:09:29Z","timestamp":1751922569000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/2\/9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,7]]},"references-count":24,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,7,7]]}},"URL":"https:\/\/doi.org\/10.62056\/ay76chdj","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,7]]},"assertion":[{"value":"2025-03-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-2-6"}}