ENSL/CWI/KCL/IRISA Joint Online Cryptography Seminars
  • iCal
  • Free Slots
  • ENS Lyon
  • CWI Amsterdam
  • King's College London
  • IRISA

Mon, 10 Jan 2022

  • Mon, 10 Jan 2022 13:00 Lattice sieving via quantum random walks by Johanna Loyer (Inria)

    Lattice-based cryptography is one of the leading proposals for post-quantum cryptography. The Shortest Vector Problem (SVP) is arguably the most important problem for the cryptanalysis of latticebased cryptography, and many lattice-based schemes have security claims based on its hardness. The best quantum algorithm for the SVP is due to Laarhoven [Laa16 PhD thesis] and runs in (heuristic) time $d^{0.2653d+o(d)}$. We present an improvement over Laarhoven’s result and present an algorithm that has a (heuristic) running time of $d^{0.2570d+o(d)}$ where $d$ is the lattice dimension. We also present time-memory trade-offs where we quantify the amount of quantum memory and quantum random access memory of our algorithm. The core idea is to replace Grover’s algorithm used in [Laa16 PhD thesis] in a key part of the sieving algorithm by a quantum random walk in which we add a layer of local sensitive filtering.

    Speaker Bio: ⯆

    2nd year PhD student at Inria Paris advised by André Chailloux.

    Venue: Online