RISC Seminars (Research on Information Security and Cryptology)

     Archives: [2023] [2022] [2021] [2020] [2019] [2018] [2017] [2016] [2015] [2014] [2013] [2012] [2011] [2010] [2009] [2008] [2007] [2006] [2005] [2004] [List of Speakers]
(To receive information about upcoming seminars, register for the RISC mailing list.)
Special RISC Seminar on Lattice-based Cryptography (on the Occasion of Wessel van Woerden's PhD defense)
Date:Wednesday, February 22nd
Location:CWI L017
14:00Wessel van Woerden (University of Bordeaux):
The Lattice Isomorphism Problem, Cryptography, and the Signature Scheme HAWK.
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.
15:00Alice Pellet--Mary (University of Bordeaux):
Theoretical hardness of the NTRU problem
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.
16:30Phong Nguyen (Ecole Normale Superieure Paris, Inria):
Taming the Hybrid Attack on NTRU
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.