Algorithms For Solving The Learning With Errors Problem

Abstract

Denne avhandlinga ser på fire ulike algoritmar for å løyse "Learning with Errors" (LWE, Læring med Feil) problemet.

Den første, BKW-algoritmen, kan samanliknas med gaussisk eliminasjon. Deretter viser vi at LWE kan reduserast til eit "Closest Vector Problem" (CVP, Nærmaste Vektor Problem) i eit gitter. Derfor ser vi på to basisreduksjonsalgoritmar for gitter: LLL og BKZ. For alle desse tre algoritmane ser vi på korleis dei fungerer, kompleksiteten og eventuelle eigenskapar som skulle følgje.

Til sist ser vi korleis vi kan bruke gitter til å løyse eit problem i ringversjonen av LWE. Vi bruker avrundingsalgoritmen for CVP for å finne ein kort generator for eit hovudideal, gitt ein lang generator.

This thesis looks at four different algorithms for solving the Learning with Errors (LWE) problem.

The first algorithm, BKW, is comparable to Gaussian elimination. Then, we show that LWE can be reduced to a Closest Vector Problem (CVP) in a lattice. Consequently, we look at two algorithms for lattice basis reduction: LLL and BKZ. For all these three algorithms we investigate how they work, their complexity and some properties that come as a result.

Lastly, we look at how we can use lattices and CVP to solve a problem in the ring version of LWE. We use the round-off algorithm for CVP to find a short generator of a principal ideal, given a long generator.