Notes on Lattice-Based Cryptography
Abstract
Asymmetrisk kryptering er avhengig av antakelsen om at noen beregningsproblemer er vanskelige å løse. I 1994 viste Peter Shor at de to mest brukte beregningsproblemene, nemlig det diskrete logaritmeproblemet og primtallsfaktorisering, ikke lenger er vanskelige å løse når man bruker en kvantedatamaskin. Siden den gang har forskere jobbet med å finne nye beregningsproblemer som er motstandsdyktige mot kvanteangrep for å erstatte disse to. Gitterbasert kryptografi er forskningsfeltet som bruker kryptografiske primitiver som involverer vanskelige problemer definert på gitter, for eksempel det korteste vektorproblemet og det nærmeste vektorproblemet. NTRU-kryptosystemet, publisert i 1998, var et av de første som ble introdusert på dette feltet. Problemet Learning With Error (LWE) ble introdusert i 2005 av Regev, og det regnes nå som et av de mest lovende beregningsproblemene som snart tas i bruk i stor skala. Å studere vanskelighetsgraden og å finne nye og raskere algoritmer som løser den, ble et ledende forskningstema innen kryptografi.
Denne oppgaven inkluderer følgende bidrag til feltet:
- En ikke-triviell reduksjon av Mersenne Low Hamming Combination Search Problem, det underliggende problemet med et NTRU-lignende kryptosystem, til Integer Linear Programming (ILP). Særlig finner vi en familie av svake nøkler.
- En konkret sikkerhetsanalyse av Integer-RLWE, en vanskelig beregningsproblemvariant av LWE, introdusert av Gu Chunsheng. Vi formaliserer et meet-in-the-middle og et gitterbasert angrep for denne saken, og vi utnytter en svakhet ved parametervalget gitt av Gu, for å bygge et forbedret gitterbasert angrep.
- En forbedring av Blum-Kalai-Wasserman-algoritmen for å løse LWE. Mer spesifikt, introduserer vi et nytt reduksjonstrinn og en ny gjetteprosedyre til algoritmen. Disse tillot oss å utvikle to implementeringer av algoritmen, som er i stand til å løse relativt store LWE-forekomster. Mens den første effektivt bare bruker RAM-minne og er fullt parallelliserbar, utnytter den andre en kombinasjon av RAM og disklagring for å overvinne minnebegrensningene gitt av RAM.
- Vi fyller et tomrom i paringsbasert kryptografi. Dette ved å gi konkrete formler for å beregne hash-funksjon til G2, den andre gruppen i paringsdomenet, for Barreto-Lynn-Scott-familien av paringsvennlige elliptiske kurver. Public-key Cryptography relies on the assumption that some computational problems are hard to solve. In 1994, Peter Shor showed that the two most used computational problems, namely the Discrete Logarithm Problem and the Integer Factoring Problem, are not hard to solve anymore when using a quantum computer. Since then, researchers have worked on finding new computational problems that are resistant to quantum attacks to replace these two. Lattice-based Cryptography is the research field that employs cryptographic primitives involving hard problems defined on lattices, such as the Shortest Vector Problem and the Closest Vector Problem. The NTRU cryptosystem, published in 1998, was one of the first to be introduced in this field. The Learning With Error (LWE) problem was introduced in 2005 by Regev, and it is now considered one of the most promising computational problems to be employed on a large scale in the near future. Studying its hardness and finding new and faster algorithms that solve it became a leading research topic in Cryptology.
This thesis includes the following contributions to the field:
- A non-trivial reduction of the Mersenne Low Hamming Combination Search Problem, the underlying problem of an NTRU-like cryptosystem, to Integer Linear Programming (ILP). In particular, we find a family of weak keys.
- A concrete security analysis of the Integer-RLWE, a hard computational problem variant of LWE introduced by Gu Chunsheng. We formalize a meet-in-the-middle attack and a lattice-based attack for this case, and we exploit a weakness of the parameters choice given by Gu to build an improved lattice-based attack.
- An improvement of the Blum-Kalai-Wasserman algorithm to solve LWE. In particular, we introduce a new reduction step and a new guessing procedure to the algorithm. These allowed us to develop two implementations of the algorithm that are able to solve relatively large LWE instances. While the first one efficiently uses only RAM memory and is fully parallelizable, the second one exploits a combination of RAM and disk storage to overcome the memory limitations given by the RAM.
- We fill a gap in Pairing-based Cryptography by providing concrete formulas to compute hash-maps to G2, the second group in the pairing domain, for the Barreto-Lynn-Scott family of pairing-friendly elliptic curves.
Has parts
Paper I: A. Budroni and A. Tenti, “The Mersenne Low Hamming Combination Search Problem Can Be Reduced to an ILP Problem," Progress in Cryptology - AFRICACRYPT 2019. Vol. 11627 of LNCS, pp. 41-55, Springer, 2019, Rabat, Morocco. The article is available at: https://hdl.handle.net/1956/21939Paper II: A. Budroni, B. Chetioui and E. Franch, “Attacks on Integer-RLWE," Information and Communications Security: 22nd International Conference (ICICS), Proceedings. Vol. 12282 of LNCS, pp. 528-542, Springer, 2020, Copenhagen, Denmark. The article is available at: https://hdl.handle.net/11250/2756488
Paper III: A. Budroni, Q. Guo, T. Johansson, E. Mårtensson and P. Stankovski Wagner, “Improvements on Making BKW Practical for LWE", Cryptography, 5(4), 31, 2021. The article is available at: https://hdl.handle.net/11250/2976696
Paper IV: A. Budroni and F. Pintore, “Efficient Hash Maps to G2 on BLS Curves", Applicable Algebra in Engineering, Communication and Computing, 33, pp. 261-281, 2022. The article is available at: https://hdl.handle.net/11250/2756472