Bridging the Gap Between Lattice Coding and Lattice Cryptography - Post-Quantum Cryptography
Lead Research Organisation:
Royal Holloway University of London
Department Name: Information Security
Abstract
Abstracts are not currently available in GtR for all funded research. This is normally because the abstract was not required at the time of proposal submission, but may be because it included sensitive information such as personal details.
Publications
| Description | 1. There are several classes of so-called "post-quantum" computational problems, i.e. computational problems that are hard even on a quantum computer. Two such classes are "lattices" (the focus of this project) and "codes". Both of these can be described as "linear algebra with small noise" but what "small" means differs between the two. Roughly speaking, the former considers the Euclidean distance the latter the Hamming distance. For lattices we have a rich theory of reduction, a theory which was not developed in the case of codes. In "An Algorithmic Reduction Theory for Binary Codes: LLL and more" first steps were taken to remedy this gap. 2. Attacks on cryptographic schemes often try to side-step the mathematical guarantees they provide by exploiting "side-channel" information. This then leads to a computational optimisation problem where a "small" (in the sense of the Euclidean distance) element is searched for that satisfies some additional constraint. In our work "On Bounded Distance Decoding with Predicate: Breaking the "Lattice Barrier" for the Hidden Number Problem" we formalise this problem and show that finding such an element is often not much more expensive than finding an arbitrarily equally short element, i.e. without the additional constraint. This then allows to reduce the data complexity for these side-channel attacks and opens the door for further applications of "lattice reduction" algorithms. |
| Exploitation Route | Certification labs often have to assess the resistance of cryptographic implementations against side-channel attacks, our BDD with predicate software (also available as a self-contained Docker container) can be used to streamline this process. |
| Sectors | Digital/Communication/Information Technologies (including Software) |
| URL | https://github.com/malb/bdd-predicate/,https://github.com/lducas/CodeRed |
| Description | - Our data https://github.com/jschanck/eprint-2019-1161 has been used in NIST PQC Round 3 submissions (e.g. https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf ) and beyond - Our code at https://github.com/malb/bdd-predicate/ for augmenting lattice algorithms with the ability to identify a distinguished point is being used by side-channel analysis professionals according to informal feedback. |
| First Year Of Impact | 2020 |
| Sector | Digital/Communication/Information Technologies (including Software) |
| Impact Types | Economic |
| Description | ERC Consolidator Grant |
| Amount | € 1,900,000 (EUR) |
| Funding ID | 101079668 |
| Organisation | European Commission |
| Sector | Public |
| Country | European Union (EU) |
| Start | 09/2023 |
| End | 08/2028 |
| Title | Sieving costs in various classical/quantum cost models |
| Description | This dataset collects the "costs" of performing the central step in a lattice sieve in various cost models. Lattice sieving is the asymptotically fastest technique to solve hard lattice problems and to deploy lattice-based cryptographic schemes in practice we need to understand its concrete costs on quantum and on classical computers. There are many parameters to optimise and this dataset contains optimised costs for dimensions up to 1000 (which suffices for cryptography) |
| Type Of Material | Database/Collection of data |
| Year Produced | 2020 |
| Provided To Others? | Yes |
| Impact | This dataset is used by others to estimate costs of lattice sieving, e.g. https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf or our own https://github.com/malb/lattice-estimator/ |
| URL | https://github.com/jschanck/eprint-2019-1161 |
| Title | Bounded Distance Decoding with Predicate |
| Description | This repository contains the Python/Sagemath source code for solving Bounded Distance Decoding augmented with a predicate characterising the target. These problem instances arise in the side-channel analysis of cryptographic schemes. |
| Type Of Technology | Software |
| Year Produced | 2020 |
| Impact | Informally, testing labs report using our software. |