Date de l'exposé : 27 janvier 2023
On the Lattice Isomorphism Problem, Quadratic Forms, Remarkable Lattices, and Cryptography
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 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 NTRU, 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 realisations of this natural idea (independently of the chosen remarkable lattice) by basing cryptography on the Lattice Isomorphism Problem (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 a poly-logarithmic approximation factor, provided that the dual lattice is also close to Minkowski’s bound.
Additionally, in this talk, I will discuss a concrete instantiation of a simple signature scheme based on (module) LIP and the trivial orthogonal lattice Z^n, named HAWK. The resulting scheme has smaller signatures than Falcon, is 2-4x as fast, and does not require high-precision floating-point arithmetic making it suitable for low end devices.
