# 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).