Paper 2022/1155

Hawk: Module LIP makes Lattice Signatures Fast, Compact and Simple

Léo Ducas, Centrum Wiskunde & Informatica, Leiden University
Eamonn W. Postlethwaite, Centrum Wiskunde & Informatica
Ludo N. Pulles, Centrum Wiskunde & Informatica
Wessel van Woerden, Centrum Wiskunde & Informatica
Abstract

We propose the signature scheme Hawk, a concrete instantiation of proposals to use the Lattice Isomorphism Problem (LIP) as a foundation for cryptography that focuses on simplicity. This simplicity stems from LIP, which allows the use of lattices such as $\mathbb{Z}^n$ , leading to signature algorithms with no floats, no rejection sampling, and compact precomputed distributions. Such design features are desirable for constrained devices, and when computing signatures inside FHE or MPC. The most significant change from recent LIP proposals is the use of module lattices, reusing algorithms and ideas from NTRUSign and Falcon. Its simplicity makes Hawk competitive. We provide cryptanalysis with experimental evidence for the design of Hawk and implement two parameter sets, Hawk-512 and Hawk-1024. Signing using Hawk-512 and Hawk-1024 is four times faster than Falcon on x86 architectures, produces signatures that are about 15% more compact, and is slightly more secure against forgeries by lattice reduction attacks. When floating-points are unavailable, Hawk signs 15 times faster than Falcon. We provide a worst case to average case reduction for module LIP. For certain parametrisations of Hawk this applies to secret key recovery and we reduce signature forgery in the random oracle model to a new problem called the one more short vector problem.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Post-Quantum Cryptography Signatures Module Lattice Isomorphism Problem Concrete Design Quadratic Forms
Contact author(s)
ducas @ cwi nl
ewp @ cwi nl
lnp @ cwi nl
wvw @ cwi nl
History
2022-09-05: approved
2022-09-05: received
See all versions
Short URL
https://ia.cr/2022/1155
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1155,
      author = {Léo Ducas and Eamonn W. Postlethwaite and Ludo N. Pulles and Wessel van Woerden},
      title = {Hawk: Module LIP makes Lattice Signatures Fast, Compact and Simple},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1155},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1155}},
      url = {https://eprint.iacr.org/2022/1155}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.