Paper 2021/1332

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

Léo Ducas
Wessel van Woerden
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.

Note: Update (Oct 11, 2021) : Genus now included in the arithmetic invariants + genus match for our instantiations. Update (Mar 1, 2021) : Included section about the `hull' of a lattice. Update (Sep 19, 2022) : Fixed issue in proof of Lemma 3.4, made definition and sampling algorithm of the equivalence class distribution identical.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2022
DOI
10.1007/978-3-031-07082-2_23
Keywords
lattice techniques lattice isomorphism problem quadratic forms foundations identification protocols public-key cryptography key encapsulation mechanism signature zero knowledge
Contact author(s)
l ducas @ cwi nl
wesselvanwoerden @ gmail com
History
2022-09-19: last of 3 revisions
2021-10-05: received
See all versions
Short URL
https://ia.cr/2021/1332
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1332,
      author = {Léo Ducas and Wessel van Woerden},
      title = {On the Lattice Isomorphism Problem, Quadratic Forms, Remarkable Lattices, and Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1332},
      year = {2021},
      doi = {10.1007/978-3-031-07082-2_23},
      note = {\url{https://eprint.iacr.org/2021/1332}},
      url = {https://eprint.iacr.org/2021/1332}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.