Cyber Security Seminar on Quantum Cryptanalysis of Lattice Problems

Seminar
This event has now finished.
  • Date and time: Tuesday 1 December 2020, 3.30pm to 4.30pm
  • Location: Online (Zoom)
  • Admission: Free admission

Event details

In this talk Eamonn will give an introduction to the learning with errors (LWE) problem, a versatile lattice problem with a "worst case to average case" reduction from conjectured quantum hard problems.

Two recent results will be discussed:

The first is work with Fernando Virdia in which we account for probabilistic effects in the "primal attack" – an attack that reduces LWE to the unique shortest vector problem (uSVP) and uses lattice reduction to solve it. This allows us to explain results from experimental works where slightly less expensive lattice reduction than expected had a non zero chance of solving given LWE instances.

The second work, joint with Martin Albrecht, Vlad Gheorghiu and John Schanck, concerns lattice reduction itself, which makes calls to a shortest vector problem (SVP) oracle. The cost of these oracle calls is the critical quantity to consider when determining the cost of lattice reduction. We design quantum circuits for a class of SVP solvers called "lattice sieves" and optimise them under several pertinent metrics. Ultimately we conclude that there is little quantum advantage in the cryptographically relevant domain.
 

(Meeting ID: 985 6294 4526, Passcode: 463058)

Eamonn Postlethwaite (RHUL)

Eamonn Postlethwaite is a final year Ph.D student at Royal Holloway, under Martin Albrecht. His work focuses mainly on practical lattice based cryptanalysis. He is currently on an internship at PQShield in Oxford, where he is designing lattice based interactive argument systems.

Contact us

+44 (0)1904 325501
Department of Computer Science, University of York, York YO10 5GH