HAWK: Having Automorphisms Weakens Key
Authors
Daniël M. H. van Gent, Ludo N. Pulles
Daniël M. H. van Gent
Centrum Wiskunde & Informatica, Amsterdam, the Netherlands
daniel dot van dot gent at cwi dot nl
daniel dot van dot gent at cwi dot nl
Ludo N. Pulles
Centrum Wiskunde & Informatica, Amsterdam, the Netherlands
lnp at cwi dot nl
lnp at cwi dot nl
Abstract
The search rank-2 module Lattice Isomorphism Problem (smLIP), over a cyclotomic ring of degree a power of two, can be reduced to an instance of the Lattice Isomorphism Problem (LIP) of at most half the rank if an adversary knows a nontrivial automorphism of the underlying integer lattice. Knowledge of such a nontrivial automorphism speeds up the key recovery attack on HAWK at least quadratically, which would halve the number of security bits.
Luo et al. (ASIACRYPT 2024) recently found an automorphism that breaks omSVP, the initial underlying hardness assumption of HAWK. The team of HAWK amended the definition of omSVP to include this so-called symplectic automorphism in their submission to the second round of NIST's standardization of additional signatures. This work provides confidence in the soundness of this updated definition, assuming smLIP is hard, since there are plausibly no more trivial automorphisms that allow winning the omSVP game easily.
Although this work does not affect the security of HAWK, it opens up a new attack avenue involving the automorphism group that may be theoretically interesting on its own.
References
[AD21]
Martin R. Albrecht and Léo Ducas. Lattice Attacks on NTRU and LWE: A History of Refinements, pages 15–40. Cambridge University Press, Cambridge, United Kingdom 2021. DOI: 10.1017/9781108854207
[ADPS16]
Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum Key Exchange - A New Hope. In Thorsten Holz and Stefan Savage, editors, USENIX Security 2016: 25th USENIX Security Symposium, pages 327–343, Austin, TX, USA. 2016. USENIX Association.
[AGVW17]
Martin R. Albrecht, Florian Göpfert, Fernando Virdia, and Thomas Wunderer. Revisiting the Expected Cost of Solving uSVP and Applications to LWE. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, Part I, volume 10624 of Lecture Notes in Computer Science, pages 297–322, Hong Kong, China. 2017. Springer, Cham, Switzerland. DOI: 10.1007/978-3-319-70694-8_11
[APvW25]
Bill Allombert, Alice Pellet-Mary, and Wessel P. J. van Woerden. Cryptanalysis of Rank-2 Module-LIP: A Single Real Embedding Is All It Takes. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology – EUROCRYPT 2025, Part II, volume 15602 of Lecture Notes in Computer Science, pages 184–212, Madrid, Spain. 2025. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-91124-8_7
[BBD+24]
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. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/Projects/pqc-dig-sig/round-2-additional-signatures. 2024.
[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, Advances in Cryptology – EUROCRYPT 2023, Part V, volume 14008 of Lecture Notes in Computer Science, pages 252–281, Lyon, France. 2023. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-30589-4_9
[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
[BN24]
Henry Bambury and Phong Q. Nguyen. Improved Provable Reduction of NTRU and Hypercubic Lattices. In Markku-Juhani Saarinen and Daniel Smith-Tone, editors, Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Part I, pages 343–370, Oxford, UK. 2024. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-62743-9_12
[BSW18]
Shi Bai, Damien Stehlé, and Weiqiang Wen. Measuring, Simulating and Exploiting the Head Concavity Phenomenon in BKZ. In Thomas Peyrin and Steven Galbraith, editors, Advances in Cryptology – ASIACRYPT 2018, Part I, volume 11272 of Lecture Notes in Computer Science, pages 369–404, Brisbane, Queensland, Australia. 2018. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-03326-2_13
[Che13]
Yuanmi Chen. Réduction de réseau et sécurité concrete du chiffrement completement homomorphe. PhD Thesis. Université Paris Diderot, 2013.
[CME+25]
Clémence Chevignard, Guilhem Mureau, Thomas Espitau, Alice Pellet-Mary, Heorhii Pliatsok, and Alexandre Wallet. A Reduction from Hawk to the Principal Ideal Problem in a Quaternion Algebra. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology – EUROCRYPT 2025, Part II, volume 15602 of Lecture Notes in Computer Science, pages 154–183, Madrid, Spain. 2025. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-91124-8_6
[CN11]
Yuanmi Chen and Phong Q. Nguyen. BKZ 2.0: Better Lattice Security Estimates. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology – ASIACRYPT 2011, volume 7073 of Lecture Notes in Computer Science, pages 1–20, Seoul, South Korea. 2011. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-642-25385-0_1
[CS98]
J.H. Conway and N.J.A. Sloane. Sphere Packings, Lattices and Groups, volume 3 of Grundlehren der mathematischen Wissenschaften. Grundlehren der mathematischen Wissenschaften. Springer New York 1998. DOI: 10.1007/978-1-4757-6568-7
[DDGR20]
Dana Dachman-Soled, Léo Ducas, Huijing Gong, and Mélissa Rossi. LWE with Side Information: Attacks and Concrete Security Estimation. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, Part II, volume 12171 of Lecture Notes in Computer Science, pages 329–358, Santa Barbara, CA, USA. 2020. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-56880-1_12
[DN12]
Léo Ducas and Phong Q. Nguyen. Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures. In Xiaoyun Wang and Kazue Sako, editors, Advances in Cryptology – ASIACRYPT 2012, volume 7658 of Lecture Notes in Computer Science, pages 433–450, Beijing, China. 2012. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-642-34961-4_27
[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, Advances in Cryptology – ASIACRYPT 2022, Part IV, volume 13794 of Lecture Notes in Computer Science, pages 65–94, Taipei, Taiwan. 2022. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-22972-5_3
[Duc24]
Léo Ducas. Provable lattice reduction of ${\mathbb{Z}}^n$ with blocksize n/2. Designs, Codes and Cryptography, 92(4):909–916, 2024. DOI: 10.1007/s10623-023-01320-7
[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, Advances in Cryptology – EUROCRYPT 2022, Part III, volume 13277 of Lecture Notes in Computer Science, pages 643–673, Trondheim, Norway. 2022. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-07082-2_23
[GPV08]
Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 197–206. 2008. ACM. DOI: 10.1145/1374376.1374407
[GS02]
Craig Gentry and Michael Szydlo. Cryptanalysis of the Revised NTRU Signature Scheme. In Lars R. Knudsen, editor, Advances in Cryptology – EUROCRYPT 2002, volume 2332 of Lecture Notes in Computer Science, pages 299–320, Amsterdam, The Netherlands. 2002. Springer Berlin Heidelberg, Germany. DOI: 10.1007/3-540-46035-7_20
[JWL+23]
Kaijie Jiang, Anyu Wang, Hengyi Luo, Guoxiao Liu, Yang Yu, and Xiaoyun Wang. Exploiting the Symmetry of $\mathbb {{Z}}^n$: Randomization and the Automorphism Problem. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology – ASIACRYPT 2023, Part IV, volume 14441 of Lecture Notes in Computer Science, pages 167–200, Guangzhou, China. 2023. Springer, Singapore, Singapore. DOI: 10.1007/978-981-99-8730-6_6
[LJPW24]
Hengyi Luo, Kaijie Jiang, Yanbin Pan, and Anyu Wang. Cryptanalysis of Rank-2 Module-LIP with Symplectic Automorphisms. In Kai-Min Chung and Yu Sasaki, editors, Advances in Cryptology – ASIACRYPT 2024, Part IV, volume 15487 of Lecture Notes in Computer Science, pages 359–385, Kolkata, India. 2024. Springer, Singapore, Singapore. DOI: 10.1007/978-981-96-0894-2_12
[LS17]
Hendrik W. Lenstra Jr. and Alice Silverberg. Lattices with Symmetry. Journal of Cryptology, 30(3):760–804, July 2017. DOI: 10.1007/s00145-016-9235-7
[LS19]
Hendrik W. Lenstra Jr. and Alice Silverberg. Testing Isomorphism of Lattices over CM-Orders. SIAM Journal on Computing, 48(4):1300-1334, 2019. DOI: 10.1137/17M115390X
[MPPW24]
Guilhem Mureau, Alice Pellet-Mary, Georgii Pliatsok, and Alexandre Wallet. Cryptanalysis of Rank-2 Module-LIP in Totally Real Number Fields. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, Part VII, volume 14657 of Lecture Notes in Computer Science, pages 226–255, Zurich, Switzerland. 2024. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-58754-2_9
[NR09]
Phong Q. Nguyen and Oded Regev. Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures. Journal of Cryptology, 22(2):139–160, April 2009. DOI: 10.1007/s00145-008-9031-0
[PV21]
Eamonn W. Postlethwaite and Fernando Virdia. On the Success Probability of Solving Unique SVP via BKZ. In Juan Garay, editor, PKC 2021: 24th International Conference on Theory and Practice of Public Key Cryptography, Part I, volume 12710 of Lecture Notes in Computer Science, pages 68–98, Virtual Event. 2021. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-75245-3_4
[Szy03]
Michael Szydlo. Hypercubic Lattice Reduction and Analysis of GGH and NTRU Signatures. In Eli Biham, editor, Advances in Cryptology – EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 433–448, Warsaw, Poland. 2003. Springer Berlin Heidelberg, Germany. DOI: 10.1007/3-540-39200-9_27
PDF
History
Submitted: 2025-04-07
Accepted: 2025-06-02
Published: 2025-07-07
Accepted: 2025-06-02
Published: 2025-07-07
How to cite
Daniël M. H. van Gent and Ludo N. Pulles, HAWK: Having Automorphisms Weakens Key. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/a3qjp2w9p.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.