Some Algorithms for Learning with Errors

Robert Fitzpatrick

Research output: ThesisDoctoral Thesis

1861 Downloads (Pure)

Abstract

The Learning with Errors (LWE) problem, introduced in 2005 by Regev, is a generalisation to larger modulii of the Learning Parity with Noise problem and has proven to be a remarkably versatile primitive for the construction of cryptographic schemes. With an average-to-worst-case reduction from (assumed) hard lattice problems, the LWE problem is highly attractive as a basis for post-quantum secure constructions. However, the concrete hardness of the LWE problem remains little investigated, with parameter choices in the literature tending to be conservative or completely absent as a result. In this work we study the various known approaches for solving LWE instances and develop new and modified approaches. Two main approaches exist - those employing lattice basis reduction and combinatorial approaches. For the latter we present the first analysis and adaptation of the BKW algorithm to the LWE case, illustrating that this approach is asymptotically more efficient than known lattice- based approaches with surprisingly low `crossover' dimension`. We also present a modification of the BKW algorithm, optimised for LWE instances in which the secret vector entries are unusually small, demonstrating this modified algorithm to be significantly more efficient than previously-known approaches. We additionally examine the recently-proposed public-key scheme of Huang, Liu and Yang and show that, by viewing this scheme as a weak LWE-like problem we can break all challenges in a matter of hours. With regard to algorithms which rely on lattice basis reduction, we present the first experimental study of the efficacy of applying Kannan's embedding approach, showing that this approach out-performs the classical distinguishing approach in the high-advantage regime.
Original languageEnglish
QualificationPh.D.
Awarding Institution
  • Royal Holloway, University of London
Supervisors/Advisors
  • Cid, Carlos, Supervisor
  • Martin, Keith M., Advisor
Award date1 Sept 2014
Publication statusUnpublished - 21 Aug 2014

Cite this