International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the Lattice Isomorphism Problem, Quadratic Forms, Remarkable Lattices, and Cryptography

Authors:
Wessel van Woerden , CWI, Cryptology Group, Amsterdam
Léo Ducas , CWI, Cryptology Group, Amsterdam and Leiden University, Mathematical Institute, Leiden
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: A natural and recurring idea in the knapsack/lattice cryptography literature is to start from a lattice with remarkable decoding capability as your private key, and hide it somehow to make a public key. This is also how the code-based encryption scheme of McEliece (1978) proceeds. This idea has never worked out very well for lattices: ad-hoc approaches have been proposed, but they have been subject to ad-hoc attacks, using tricks beyond lattice reduction algorithms. On the other hand the framework offered by the Short Integer Solution (SIS) and Learning With Errors (LWE) problems, while convenient and well founded, remains frustrating from a coding perspective: the underlying decoding algorithms are rather trivial, with poor decoding performance. In this work, we provide generic realizations of this natural idea (independently of the chosen remarkable lattice) by basing cryptography on the lattice isomorphism problem (LIP). More specifically, we provide: - a worst-case to average-case reduction for search-LIP and distinguish-LIP within an isomorphism class, by extending techniques of Haviv and Regev (SODA 2014). - a zero-knowledge proof of knowledge (ZKPoK) of an isomorphism. This implies an identification scheme based on search-LIP. - a key encapsulation mechanism (KEM) scheme and a hash-then-sign signature scheme, both based on distinguish-LIP. The purpose of this approach is for remarkable lattices to improve the security and performance of lattice-based cryptography. For example, decoding within poly-logarithmic factor from Minkowski's bound in a remarkable lattice would lead to a KEM resisting lattice attacks down to poly-logarithmic approximation factor, provided that the dual lattice is also close to Minkowski's bound. Recent works have indeed reached such decoders for certain lattices (Chor-Rivest, Barnes-Sloan), but these do not perfectly fit our need as their duals have poor minimal distance.
Video from EUROCRYPT 2022
BibTeX
@inproceedings{eurocrypt-2022-31887,
  title={On the Lattice Isomorphism Problem, Quadratic Forms, Remarkable Lattices, and Cryptography},
  publisher={Springer-Verlag},
  author={Wessel van Woerden and Léo Ducas},
  year=2022
}