ENS Lyon -- ENS Paris monthly lattice meetings

The meetings are organized by Vadim Lyubashevsky and Damien Stehlé, and financially supported by ANR CLE and Horizon2020, SAFEcrypto and ERC Starting Grant ERC-2013-StG-335086-LATTAC.
If you want to attend, please contact the organizers: precise headcount is required to book appropriate rooms.

**Next meeting**: Wednesday, 10 June 2015

Location: Lyon.
Room: 115.

11:00, Rafael del Pino (ENS Paris), Simple and practical lattice-based AKE

I will present a new simple construction that uses NTRU lattices and a few ad-hoc tricks to allow us to obtain a lattice based forward secure AKE with keys and communication under 1KB. The AKE comes from a generic construction that uses a public key encryption scheme and a signature scheme. We improve upon this construction by considering an NTRU PKE with non negligible error probability (this does not hurt security as the public keys are ephemeral) and by adapting a Hash-and-Sign signature scheme to work in message recovery mode.

Joint work with Vadim Lyubashevsky and David Pointcheval

14:30, Thijs Laarhoven (TU/e), Sieving for shortest vectors in lattices using locality-sensitive hashing

Most lattice-based cryptographic primitives rely on the shortest vector problem (SVP) on lattices being hard. To assess the computational hardness of SVP and breaking these schemes, one commonly relies on the estimated time complexity of enumeration for solving SVP. In 2001 the breakthrough work of Ajtai et al. showed that SVP can actually be solved faster in high dimensions, using a technique called sieving. Although this technique seemed impractical at first, various improvements have since shown that sieving may be competitive with enumeration after all. In this talk we will look at recent advances in sieving using a technique from nearest neighbor searching, locality-sensitive hashing.

The talk will be mostly based on this article but will include fragments of this one, this one and this one.

Recommended preparatory reading:

Past meetings

Wednesday, 6 May 2015

Location: Paris.
Room: S16.

11:00, Noah Stephens-Davidowitz (NYU), SVP in 2^n Time Using Discrete Gaussian Sampling

I will present a 2^(n+o(n))-time algorithm for the shortest vector problem on lattices (improving on the previous best-known algorithm of Micciancio and Voulgaris, which runs in time 2^(2n+o(n))). The algorithm uses the elementary yet powerful observation that, by properly combining samples from a Gaussian distribution over the lattice, we can produce exact samples from a narrower Gaussian distribution on the lattice. We use this to sample from an arbitrarily narrow Gaussian distribution over the lattice, allowing us to find a shortest vector.

If time allows and interest merits, we can discuss the generalization of this algorithm to solve CVP in the same asymptotic running time.

Based on joint work with Divesh Aggarwal, Daniel Dadush, and Oded Regev, available here.

14:30, Nicolas Gama (UVSQ), Towards an efficient fully homomorphic machine

We provide a somewhat conceptually simpler generalization of the Alperin-Sheriff-Peikert variant of the Gentry-Sahai-Waters homomorphic scheme, based on any black-box LWE-like cryptosystem. After realizing that the mux gate is a very good homomorphic primitive, we obtain a somewhat homomorphic scheme where any arbitrary boolean function can be evaluated in a systematic way with a noise overhead proportional to the square root of its number of variables, and similarly, we may also recognize any arbitrary regular language with a noise overhead proportional to the square-root length of the tested word. Since the systematic transcription of the decryption function itself is a polynomial circuit with only a linear noise overhead, this allows for instance, to create an efficient fully homomorphic machine, which simulates some simple 16-bit processor, whose assembly supports a few arithmetic operations, memory load and store, and pointer dereference. The whole system relies on a worst case lattice hardness with at most cubic factors.
Suggested preparatory reading:

Wednesday, 25 March 2015

Location: Lyon.
Room: 115 (exact sciences campus, main building, level 1).

11:00, Paul Kirchner (ENS Paris), An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices

We introduce a new variant of the Blum, Kalai and Wasserman algorithm, which yields a sub-exponential algorithm when the secret is small (for example, binary). We then introduce variants of BDD, GapSVP and UniqueSVP, where the target point is required to lie in the fundamental parallelepiped, and show how our algorithm is able to solve these variants in subexponential time. Moreover, we also show how it can be used to solve the BinaryLWE problem with a linear number of samples, and therefore heuristically breaks NTRU in subexponential time.

14:30, Tancrède Lepoint (CryptoExperts), CLT: Recent Attacks and A New Tentative Reparation

One week after Cheon, Han, Lee, Ryu and Stehlé's attack on CLT (presented by Damien on March 4th), the attack has been slightly extended and new fixes for CLT were suggested on the IACR Eprint Archive. Three weeks later, the fixes were shown to be insecure. In this talk, I will present: (1) a small survey of new attacks generalizing Cheon et al.’s attack on CLT and suggested fixes (joint work with Coron, Gentry, Halevi, Maji, Miles, Raykova, Sahai and Tibouchi) (2) a new CLT candidate designed to resist Cheon et al.’s attack, in which the SubM and DLIN assumptions might still hold (joint work with Coron and Tibouchi).

Wednesday, 4 March 2015

Location: Paris.
Room W. See here.

11:00, Adeline Langlois (EPFL), GGH multilinear maps

The GGH graded encoding scheme, introduced by Garg, Gentry and Halevi in 2013, is the first plausible approximation to a cryptographic multilinear map. In this talk, I will introduce the GGH scheme and his more efficient variant GGHLite. Then I will present the improvements we made to provide an efficient implementation of GGHLite and of the N-partite Diffie-Hellman key exchange.
The talk is based on:

14:30, Damien Stehlé (ENS Lyon), Zeroizing attacks on multilinear maps

I will describe so-called zeroizing attacks on multilinear maps. In the case of the GGH multilinear map, zeroizing allows to break the multilinear extensions of the Subgroup Membership and Decision Linear problems. In the case of the multilinear map of Coron, Lepoint and Tibouchi, zeroizing leads to a total break.
References:

Wednesday, 4 February 2015

Location: Lyon.
Room: 115 (exact sciences campus, main building, level 1).

11:00, Léo Ducas (CWI), Exploration of Dirichlet Unit Theorem Log(Z[\zeta_{2^k}]*)

Finding a short generator of a principal ideal of some ring R can be reduced to solving a Close Vector Problem (CVP) instance in a *fixed* lattice, namely the Dirichlet Unit lattice of R. We study the geometry of this lattice when R is the (2^k)-th cyclotomic ring, hoping to solve some CVP in sub-exponential time. This talk will present (exciting) work in progress, involving algebraic number theory, geometry of numbers, algorithmics and some arithmetic.

14:30, Fabrice Benhamouda (ENS Paris), Better Zero-Knowledge Proofs for Lattice Encryption

Previously known zero-knowledge proofs of knowledge of plaintext for lattice encryption had a soundness error of 2/3 (Stern-like protocols) or 1/2 (Fiat-Shamir protocols with +-1 challenges) and needed to be repeated O(k) times for the resulting protocol to be secure (with k the security parameter). In a joint paper with Jan Camenisch, Stephan Krenn, Gregory Neven and Vadim Lyubashevsky at Asiacrypt 2014, a new Fiat-Shamir protocol with soundness error 1/(2n+1) was proposed, for Ring-LWE or NTRU-like encryption schemes over Z_p[X]/(X^n + 1). This talk will present this new protocol, extend it to other rings, and show current limitations of this method, namely that this method does not seem to enable the design of a zero-knowledge protocol with soundness error 1/2^k (without repetition).