Lattice-based approaches are emerging as a common theme in modern cryptography and coding theory. In communications, they are useful mathematical tools to construct powerful error-correction codes achieving the capacity of wireless channels. In cryptography, they are used to building lattice-based schemes with provable security, better asymptotic efficiency, resilience against quantum attacks and new functionalities such as fully homomorphic encryption.
This meeting — on Friday, 9 December 2022 — is aimed at connecting the two communities with a common interest in lattices. It will consist of several talks on related topics, with a format aimed at encouraging interaction.
We start this talk with a brief introduction and timeline about the use of lattices in secure communication, particularly discussing metrics that allow the design of reliable lattice codes for the wiretap channel. The secrecy function is one such metric, which arises from minimizing the success probability of an eavesdropper guessing a message sent through a Gaussian channel. In this context, the notion of formally unimodular lattice, a generalization of unimodular lattice, becomes fundamental. The definition, constructions, and examples of such lattices will be presented (and, even more generally, how this concept can be extended to nonlattice packings). Improvements in the performance of formally unimodular lattices compared to unimodular lattices in a Gaussian wiretap channel will be demonstrated. Finally, we will also address open problems about applying such a family of lattices to other metrics and/or in cryptography.
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 ZZ^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.
In this talk, I will define three variants of the NTRU problem. I will then present what we currently know about reductions between these variants, as well as reductions from standard lattice problems (such as the ideal shortest vector problem and the unique shortest vector problem in modules of rank 2) to one of the variants of NTRU.
This is based on joint works with Damien Stehlé and Joël Felderhoff.
SENATE-102
Senate House
University of London,
Malet St
London WC1E 7HU
Everyone is welcome. Two caveats: