Lattice-based approaches are emerging as a common theme in modern cryptography and coding theory. In communications, they are indispensable 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 15 January 2018 — is aimed at connecting the two communities in the UK with a common interest in lattices. It will consist of several talks on related topics, with a format aimed at encouraging interaction.
Lattices in Rn with orthogonal sublattices are associated with spherical codes in R2n generated by a finite commutative group of orthogonal matrices. They can also be used to construct homogeneous spherical curves for transmitting a continuous alphabet source over an AWGN channel. In both cases, the performance of the decoding process is related to the packing density of the lattices. In the continuous case, the “packing density” of these curves relies on the search for projection lattices with good packing density. It will be presented a brief survey and recent developments on this topic.
In this talk we will discuss some of the practical aspects of lattice-based and homomorphic encryption, with particular reference to associated hardware designs. Current instantiations of FHE are known to be too slow for practical use. However, the combination of both algorithmic and implementation optimisations can increase performance greatly; for example we have shown research speed improvements for FHE encryption of up to approximately 130. Lattice-based cryptography shows promise as a quantum- safe alternative to existing public-key cryptosystems. However, the performance of such schemes suffer with associated large public key sizes, which is a challenge for real world systems. Research carried out into the hardware design of encryption using standard lattices, as part of the H2020 SAFEcrypto project, will be discussed to show the potential performance improvement achieved via the proposal of optimised hardware designs; our hardware design of a standard lattice-based cryptographic scheme carries out over 1200 encryptions per second and 4300 decryptions per second, targeting the lightweight Spartan-6 FPGA platform.
Lattice codes are elegant and powerful structures that not only can achieve the capacity of the AWGN channel but also are a key ingredient to many multiterminal schemes that exploit linearity properties. However, constructing lattice codes that can realize these benefits with low complexity is still a challenging problem. In this talk, we present efficient encoding and decoding algorithms for multilevel binary LDPC lattices constructed via Construction D’ whose complexity is linear in the total number of coded bits. Moreover, we propose a generalization of Construction D’ that relaxes some of the nesting constraints on the component codes, leading to a simpler and improved design. Based on this construction, we design low-complexity multilevel LDPC lattices whose performance under multistage lattice decoding is comparable to that of polar lattices on the power-unconstrained AWGN channel and close to that of conventional (non-lattice) coded modulation schemes on the power-constrained AWGN channel.
The learning with errors (LWE) problem has received a large amount attention since its inception in 2005 as a proposed quantum hard problem. Ring-LWE and Module-LWE have been proposed in order to significantly increase the efficiency of schemes at the potential cost of a stronger hardness assumption.
Standard results suggest that Ring-LWE is a more structured (and therefore potentially easier) problem compared to Module-LWE. However, in this talk, we present an explicit reduction from Module-LWE to Ring-LWE. More importantly, the consequences of this reduction will be discussed. In particular, the reduction suggests that the hardness of Ring-LWE increases with growing modulus which agrees with observations from state-of-the-art cryptanalysis. In addition, we conclude that the Module-LWE/Ring-LWE distinction is rather artificial with respect to hardness and that there is no trivial hardness hierarchy between the two problems. In addition, a Ring-LWE self-reduction that halves the ring dimension at the cost of squaring the modulus will be discussed.
Room 611
Department of Electrical and Electronic Engineering
Imperial College London
South Kensington
London SW7 2AZ
Everyone is welcome. Two caveats: