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.
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.
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.
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.
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.
Room 909
Department of Electrical and Electronic Engineering
Imperial College London
South Kensington
London SW7 2AZ
Everyone is welcome. Two caveats: