Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS

Guo, Qian LU and Johansson, Thomas LU orcid (2021) 27th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2021 In Lecture Notes in Computer Science 13093. p.33-62
Abstract
Cryptosystems based on the learning with errors (LWE) problem are assigned a security level that relates to the cost of generic algorithms for solving the LWE problem. This includes at least the so-called primal and dual lattice attacks. In this paper, we present an improvement of the dual lattice attack using an idea that can be traced back to work by Bleichenbacher. We present an improved distinguisher that in combination with a guessing step shows a reduction in the overall complexity for the dual attack on all schemes. Our second contribution is a new two-step lattice reduction strategy that allows the new dual lattice attack to exploit two recent techniques in lattice reduction algorithms, i.e., the “dimensions for free” trick and the... (More)
Cryptosystems based on the learning with errors (LWE) problem are assigned a security level that relates to the cost of generic algorithms for solving the LWE problem. This includes at least the so-called primal and dual lattice attacks. In this paper, we present an improvement of the dual lattice attack using an idea that can be traced back to work by Bleichenbacher. We present an improved distinguisher that in combination with a guessing step shows a reduction in the overall complexity for the dual attack on all schemes. Our second contribution is a new two-step lattice reduction strategy that allows the new dual lattice attack to exploit two recent techniques in lattice reduction algorithms, i.e., the “dimensions for free” trick and the trick of producing many short vectors in one sieving. Since the incompatibility of these two tricks was believed to be the main reason that dual attacks are less interesting, our new reduction strategy allows more efficient dual approaches than primal attacks, for important cryptographic parameter sets.

We apply the proposed attacks on CRYSTALS-Kyber and CRYSTALS-Dilithium, two of the finalists in the NIST post-quantum cryptography project and present new lower complexity numbers, both classically and quantumly in the core-SVP model. Most importantly, for the proposed security parameters, our new dual attack with refined lattice reduction strategy greatly improves the state-of-the-art primal attack in the classical gate-count metric, i.e., the classical Random Access Machine (RAM) model, indicating that some parameters are really on the edge for their claimed security level. Specifically, the improvement factor can be as large as 15 bits for Kyber1024 with an extrapolation model (Albrecht et al. at Eurocrypt 2019). Also, we show that Kyber768 could be solved with classical gate complexity below its claimed security level. Last, we apply the new attack to the proposed parameters in a draft version of Homomorphic Encryption Standard (see https://homomorphicencryption.org) and obtain significant gains. For instance, we could solve a parameter set aiming for 192-bit security in 2187.0 operations in the classical RAM model. Note that these parameters are deployed in well-known Fully Homomorphic Encryption libraries. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Advances in Cryptology – ASIACRYPT 2021 : 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part IV - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part IV
series title
Lecture Notes in Computer Science
volume
13093
article number
Chapter 2
pages
33 - 62
publisher
Springer
conference name
27th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2021
conference location
Singapore
conference dates
2021-12-06 - 2021-12-10
external identifiers
  • scopus:85121910752
ISSN
0302-9743
1611-3349
ISBN
978-3-030-92068-5
978-3-030-92067-8
DOI
10.1007/978-3-030-92068-5_2
project
Lightweight Cryptography for Autonomous Vehicles
language
English
LU publication?
yes
id
292b3d98-754c-414d-95db-ee38806157f9
date added to LUP
2021-12-15 14:51:37
date last changed
2024-06-16 10:09:18
@inproceedings{292b3d98-754c-414d-95db-ee38806157f9,
  abstract     = {{Cryptosystems based on the learning with errors (LWE) problem are assigned a security level that relates to the cost of generic algorithms for solving the LWE problem. This includes at least the so-called primal and dual lattice attacks. In this paper, we present an improvement of the dual lattice attack using an idea that can be traced back to work by Bleichenbacher. We present an improved distinguisher that in combination with a guessing step shows a reduction in the overall complexity for the dual attack on all schemes. Our second contribution is a new two-step lattice reduction strategy that allows the new dual lattice attack to exploit two recent techniques in lattice reduction algorithms, i.e., the “dimensions for free” trick and the trick of producing many short vectors in one sieving. Since the incompatibility of these two tricks was believed to be the main reason that dual attacks are less interesting, our new reduction strategy allows more efficient dual approaches than primal attacks, for important cryptographic parameter sets.<br/><br/>We apply the proposed attacks on CRYSTALS-Kyber and CRYSTALS-Dilithium, two of the finalists in the NIST post-quantum cryptography project and present new lower complexity numbers, both classically and quantumly in the core-SVP model. Most importantly, for the proposed security parameters, our new dual attack with refined lattice reduction strategy greatly improves the state-of-the-art primal attack in the classical gate-count metric, i.e., the classical Random Access Machine (RAM) model, indicating that some parameters are really on the edge for their claimed security level. Specifically, the improvement factor can be as large as 15 bits for Kyber1024 with an extrapolation model (Albrecht et al. at Eurocrypt 2019). Also, we show that Kyber768 could be solved with classical gate complexity below its claimed security level. Last, we apply the new attack to the proposed parameters in a draft version of Homomorphic Encryption Standard (see https://homomorphicencryption.org) and obtain significant gains. For instance, we could solve a parameter set aiming for 192-bit security in   2<sup>187.0</sup>  operations in the classical RAM model. Note that these parameters are deployed in well-known Fully Homomorphic Encryption libraries.}},
  author       = {{Guo, Qian and Johansson, Thomas}},
  booktitle    = {{Advances in Cryptology – ASIACRYPT 2021 : 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part IV}},
  isbn         = {{978-3-030-92068-5}},
  issn         = {{0302-9743}},
  language     = {{eng}},
  month        = {{12}},
  pages        = {{33--62}},
  publisher    = {{Springer}},
  series       = {{Lecture Notes in Computer Science}},
  title        = {{Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS}},
  url          = {{http://dx.doi.org/10.1007/978-3-030-92068-5_2}},
  doi          = {{10.1007/978-3-030-92068-5_2}},
  volume       = {{13093}},
  year         = {{2021}},
}