CWI Cryptology Group

Abstract: A natural idea in the 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 talk, we discuss generic realisations of this natural idea 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, we 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.

Abstract: In this talk, I will give an overview of what we know about the theoretical hardness of the NTRU problem. We will review known attacks and known reductions, and also discuss what open questions are still to be solved, if we want to understand this problem as well as we understand LWE.

Abstract: We revisit collision attacks on NTRU, namely Odlyzko's meet-in-the-middle attack and Howgrave-Graham's hybrid attack. We introduce torus variants of locality sensitive hashing and new bases of the NTRU lattice. And we establish a connection between the success probability of the hybrid attack and the probability that a random point on an n-dimensional sphere (or a ball) lies inside a randomly shifted box. Previous analyses of the hybrid attack used heuristic methods to estimate this probability. We show that these heuristics typically lead to significant errors, and we present rigorous estimates.