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 Friday, 15 July 2022 — 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.
It is a long standing open problem to find search to decision reductions for structured versions of the decoding problem of linear codes (e.g. for quasi-cyclic codes). Such results in the lattice-based setting have been carried out using number fields: Polynomial-LWE, Ring-LWE, Module-LWE …
In this talk, I will present a function field analogue of the LWE problem. This new framework leads to another point of view on structured codes, strengthening the connections between lattice-based and code-based cryptography.
This framework can be instantiated with function field analogues of the cyclotomic number fields, namely Carlitz extensions, leading to the first search to decision reductions on various structured versions of the decoding problem, and Ring-LPN, which have applications to secure multi party computation. and to an authentication protocol.
We begin the talk by recalling the notion of single parity check with non-binary symbols. We then describe a trivial algorithm to decode single parity-check codes.
After this introduction, we present parity lattices obtained by recursively applying the single parity-check. The trivial algorithm is generalized to decode these lattices. We also describe a so-called splitting strategy for complexity reduction. Both bounded-distance decoding and list decoding are investigated. A formula to predict the performance of the proposed decoding algorithm is provided. We further give a graphical explanation of the algorithm behaviour via performance obtained on the Gaussian channel.
These principles are then applied to the decoding of several famous lattices, obtained as parity lattices, in moderate dimensions: The Barnes-Wall lattices in dimensions 64 and 128, the Leech lattice in dimension 24, a new lattice constructed as a simple application of the single parity check on the Leech lattice, and the Nebe lattice in dimension 72.
Finally, the presentation ends with a benchmark of quasi-optimal performance of dense lattices in moderate dimensions on the Gaussian channel.
In this talk, we present the first publicly verifiable lattice-based succinct non-interactive argument of knowledge (SNARK). The construction stems from a general technical toolkit that we develop to translate pairing-based schemes to lattice-based ones, and that allows us to construct the primitive which is at the heart of our SNARK construction: a new lattice-based vector commitment (VC) scheme supporting openings to constant-degree multivariate polynomial maps. The security is based on a new family of lattice-based computational assumptions, that we call k-Ring-Inhomogenous Short Integer Solution (or k-R-ISIS for short), which naturally generalizes the standard Short Integer Solution (SIS) assumption. We will also highlight some applications of our SNARK: we show how to construct lattice-based adaptor signatures based on the GPV paradigm and how to obtain the first aggregatable adaptor signatures from any assumption.
Room 611
Department of Electrical and Electronic Engineering
Imperial College London
South Kensington
London SW7 2AZ
Everyone is welcome. Two caveats: