London-ish Lattice & Coding Meeting: 29 September 2017 – Titles & Abstracts

[Martin R. Albrecht]

Hi all,

we now have finalised the programme. If you haven’t registered
yet, but intend to attend, please let us know (see blow).

## Programme ##

### 10:30 - 12:00 | Rachel Player: Parameter Selection in
Ring-LWE-based FHE ###

Fully Homomorphic Encryption (FHE) is one of the flagship
applications of lattice-based cryptography. Several FHE schemes
are based on the Ring Learning with Errors (Ring-LWE) problem. The
underlying Ring-LWE instances used in these schemes are however
somewhat different from ’typical’ Ring-LWE instances, so the FHE
setting is interesting from the point of view of security. Another
key issue in the FHE setting is that the choice of parameters also
influences the inherent noise, a feature present in all FHE
ciphertexts, which must be kept below a certain threshold or else
decryption will fail. Good understanding of the noise growth
behaviour is therefore essential to ensure correctness. In this
talk we discuss the challenge of picking parameters in the FHE
setting, balancing the requirements of security, performance and
correctness.

### 13:00 - 14:30 | Ram Zamir: Lattices in Information Theory ###

A lattice is a discrete subgroup of the Euclidean N-dimensional
space, which is closed under regular addition and reflection.

Lattices provide useful analytical and algorithmic tools for
designing codes for digital communication. In particular, lattice
codes are used for analog-to-digital conversion, a problem known
also as "vector quantization" or "lossy source coding". In the
dual "channel coding" problem, lattice codes combine coding and
modulation for noise immunity in transmitting digital data over
the additive white-Gaussian noise channel. More recently, lattice
codes were found useful for multi-user communication, in setups
such as coding with side information, interference cancellation,
network coding, and more.

What is a good lattice? how do we know it exists? how can we
construct it? The figure of merit depends, in fact, on the
application. In the talk we shall assess lattice goodness for each
of the communication problems above, and show the existence of
asymptotically good lattices as the dimension N becomes large. We
prove the existence result in two ways: first, indirectly, using
the Minkowski-Hlawka theorem; second, by randomizing a linear-code
based lattice construction ("construction A").

### 15:00 - 16:30 | Gottfried Herold: Lattice Sieving ###

One of the main approaches to solve the Shortest Vector Problem
(SVP) on lattices is Lattice Sieving, which heuristically solves
SVP in exponential (in the lattice rank) running time and memory.
In the algorithm originally proposed by M. Ajtai, R. Kumar and D.
Sivakumar, we combine pairs of lattice points to form ever shorter
lattice points. It achieves an asymptotic complexity of 2^0.415n
time and 2^0.208n memory to solve SVP, ignoring subexponential
factors.

There are currently two known techniques to asymptotically improve
the complexity or to provide more flexible time-memory trade-offs:
The first one is to use techniques from Locality Sensitive
Hashing, due to A. Becker, L. Ducas, N. Gama and T. Laarhoven. The
second technique is to combine more than two lattice points at a
time, due to S. Bai, T. Laarhoven and D. Stehle, which was later
improved by G. Herold and E. Kirshanova.

In this talk, I will first present an overview over those
techniques. Then I will explain a recent result, obtained jointly
with E. Kirshanova and T. Laarhoven, how to improve further on the
results from Herold and Kirshanova and how to combine the two
techniques to get even better time-memory trade-offs. If time
permits, I will talk about implementation challenges and open
problems.

### 16:45 - 18:15 | Martin Widmer: Counting Lattice Points ###

In this talk we discuss the problem of counting lattice points in
a given bounded subset of Euclidean space. If the set is
sufficiently "nice" one expects that the ration of volume and
lattice determinant is a reasonable estimate for this cardinality.
But what exactly does “nice” mean here, can one find such
“niceness-conditions” that are mild and easy to check in practise,
and what quantities of the lattice and the set does the error term
depend on? What can we say more when the lattice is admissible
(e.g. the Minkowski-embedding of an ideal of a totally real number
field) or at least “almost“ admissible? We hope to answer all of
these questions .

## URL ##

http://malb.io/discrete-subgroup/2017/09/29/lattice-meeting/

## Venue ##

Room 909B
Department of Electrical and Electronic Engineering
Imperial College London
South Kensington
London SW7 2AZ

## Registration ##

Everyone is welcome. Two caveats:

1. Speakers are told the audience is somewhat familiar with
lattices.
2. Please send us an email at <c.l...@imperial.ac.uk>, so that the
size of the room fits with the number of participants.

Cheers,
Cong & Martin