discrete subgroup

Lattice Coding & Crypto Meeting

Lattice-based approaches are emerging as a common theme in modern cryptography and coding theory. In communications, they are useful mathematical tools to construct powerful error-correction codes achieving the capacity of wireless channels. In cryptography, they are used to building lattice-based schemes with provable security, better asymptotic efficiency, resilience against quantum attacks and new functionalities such as fully homomorphic encryption.

This meeting — on 24 September 2018 — is aimed at connecting the two communities with a common interest in lattices. It will consist of several talks on related topics, with a format aimed at encouraging interaction.


10:30 - 12:00 | Leo Ducas: The General Sieve Kernel and New Records in Lattice Reduction

Sieving algorithms are asymptotically the fastest heuristic algorithms for solving the shortest vector problem, and therefore for solving other problems such as LWE or SIS, due to the Block-Korkine-Zolotarev lattice reduction algorithm (BKZ).

Until recently, sieving was considered as a function to be used as a blackbox SVP oracle inside BKZ. The works of Ducas (Eurocrypt 2018), and of Laarhoven and Mariano (PQCrypto 2018), however, proposed improvements to lattice reduction that go beyond this blackbox use of Sieve-style algorithms.

To formalise and generalise these new strategies, we propose the General Sieve Kernel (G6K, pronounced /ȝe.si.ka/), an abstract machine supporting a wide variety of lattice reduction strategies based on sieving algorithms. It is designed to minimise the sieving computation effort per reduction quality, and achieves this via mechanisms such as recycling and on-the-fly lifting. We provide a highly optimised, multi-threaded, tweakable, and open-source implementation of this stateful machine.

Finally, we apply G6K to various lattice challenges (SVP, LWE). Our work demonstrates that sieving significantly outperforms enumeration in dimensions achievable in practice.

Joint work with Martin R. Albrecht, Gottfried Herold, Elena Kirshanova, Eamonn Postlethwaite and Marc Stevens.

13:00 - 14:30 | Krzysztof Latuszynski: Markov chain Monte Carlo: design and optimisation

This talk will present Markov chain Monte Carlo, its motivation in statistics and its probabilistic underpinning. Design and properties of the popular MCMC algorithms, such as the Metropolis-Hastings, the Gibbs sampler, MALA and Hamiltonian Monte Carlo will be presented and their optimisation that underlines the design of adaptive MCMC methods will be discussed.

15:00 - 16:30 | James Howe: Standard Lattice-Based Key Encapsulation on Embedded Devices

In 2016, Bos et al. proposed the key exchange scheme FrodoCCS, that is also a submission to the NIST post-quantum standardization process, modified as a key encapsulation mechanism (FrodoKEM). The security of the scheme is based on standard lattices and the learning with errors problem. Due to the large parameters, standard lattice-based schemes have long been considered impractical on embedded devices. The FrodoKEM proposal actually comes with parameters that bring standard lattice-based cryptography within reach of being feasible on constrained devices. In this talk, we show how we have taken the final step of efficiently implementing the scheme on a low-cost FPGA and microcontroller devices and thus making conservative post-quantum cryptography practical on small devices.

16:45 - 18:15 | Laura Luzzi: Algebraic reduction for low-complexity lattice decoding

High-performance lattice codes for wireless and multiple antenna channels can be designed using number fields and division algebras. However, the main drawback of algebraic lattice codes is their prohibitive decoding complexity under maximum likelihood decoding. Algebraic reduction is a special lattice reduction technique which exploits the additional multiplicative structure of these codes to allow for low-complexity decoding. More precisely, this technique consists in absorbing part of the channel into the code, by approximating the channel matrix with an element of the group of units of the ring of integers in the number field, or of the group of units of the maximal order in the division algebra. This talk will revisit previous work on algebraic reduction and discuss the advantages and challenges of this technique as well as some recent applications.

18:30 - | Workshop Dinner


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


Everyone is welcome. Two caveats:

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