Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

Implementing the dual approaches for solving LWE

Maillard, Baptiste LU (2023) EITM01 20231
Department of Electrical and Information Technology
Abstract
Many of the finalists selected for the NIST post-quantum cryptography project are lattice-based and rely on a Learning With Errors problem (LWE). To solve such a problem, it is possible to implement a primal attack or a dual attack. In this context, Guo and Johansson as well as the MATZOV center have both proposed an improved dual attack against several NIST lattice candidates.

The goal of this thesis was to implement two different dual attacks, especially combine their respective distinguisher with a C++ and Python library used for lattice reduction called G6k and get their performance for a CRYSTALS-Kyber instance, one of the finalists in the NIST post-quantum cryptography project.
Popular Abstract
The observed performance of two dual lattice attacks should encourage us to develop these attacks further.

Lattice-based cryptography relying on the LWE problem is becoming more and more essential in post-quantum cryptography. Recently, Guo and Johansson as well as MATZOV have both proposed an improved dual lattice attack against several NIST lattice candidates. The results achieved by these two attacks in this work lead us to believe that the development of dual lattice attacks should be pursued.
Please use this url to cite or link to this publication:
author
Maillard, Baptiste LU
supervisor
organization
course
EITM01 20231
year
type
H1 - Master's Degree (One Year)
subject
keywords
Post-quantum cryptography, Lattice-based cryptography, Dual attacks, Learning with errors, CRYSTALS, Fast Fourier Transform
report number
LU/LTH-EIT 2023-945
language
English
id
9134968
date added to LUP
2023-08-29 10:09:30
date last changed
2024-03-01 10:25:52
@misc{9134968,
  abstract     = {{Many of the finalists selected for the NIST post-quantum cryptography project are lattice-based and rely on a Learning With Errors problem (LWE). To solve such a problem, it is possible to implement a primal attack or a dual attack. In this context, Guo and Johansson as well as the MATZOV center have both proposed an improved dual attack against several NIST lattice candidates.

The goal of this thesis was to implement two different dual attacks, especially combine their respective distinguisher with a C++ and Python library used for lattice reduction called G6k and get their performance for a CRYSTALS-Kyber instance, one of the finalists in the NIST post-quantum cryptography project.}},
  author       = {{Maillard, Baptiste}},
  language     = {{eng}},
  note         = {{Student Paper}},
  title        = {{Implementing the dual approaches for solving LWE}},
  year         = {{2023}},
}