Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Improved Estimation of Key Enumeration with Applications to Solving LWE

Budroni, Alessandro LU and Mårtensson, Erik LU orcid (2023) 2023 International Symposium on Information Theory
Abstract
In post-quantum cryptography (PQC), Learning With Errors (LWE) is one of the dominant underlying mathematical problems. For example, in NIST’s PQC standardization process, the Key Encapsulation Mechanism (KEM) protocol chosen for standardization was Kyber, an LWE-based scheme. Recently the dual attack surpassed the primal attack in terms of concrete complexity for solving the underlying LWE problem for multiple cryptographic schemes, including Kyber. The dual attack consists of a reduction part and a distinguishing part. When estimating the cost of the distinguishing part, one has to estimate the expected cost of enumerating over a certain number of positions of the secret key. Our contribution consists of giving a polynomial-time approach... (More)
In post-quantum cryptography (PQC), Learning With Errors (LWE) is one of the dominant underlying mathematical problems. For example, in NIST’s PQC standardization process, the Key Encapsulation Mechanism (KEM) protocol chosen for standardization was Kyber, an LWE-based scheme. Recently the dual attack surpassed the primal attack in terms of concrete complexity for solving the underlying LWE problem for multiple cryptographic schemes, including Kyber. The dual attack consists of a reduction part and a distinguishing part. When estimating the cost of the distinguishing part, one has to estimate the expected cost of enumerating over a certain number of positions of the secret key. Our contribution consists of giving a polynomial-time approach for calculating the expected complexity of such an enumeration procedure. This allows us to revise the complexity of the dual attack on the LWE-based protocols Kyber, Saber and TFHE. For all these schemes we improve upon the total bit-complexity in both the classical and the quantum setting.As our method of calculating the expected cost of enumeration is fairly general, it might be of independent interest in other areas of cryptography or even in other research areas. (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
IEEE International Symposium on Information Theory (ISIT)
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
conference name
2023 International Symposium on Information Theory
conference location
Taipei, Taiwan
conference dates
2023-06-25 - 2023-06-30
external identifiers
  • scopus:85171423558
ISBN
978-1-6654-7555-6
978-1-6654-7554-9
DOI
10.1109/ISIT54713.2023.10206474
language
English
LU publication?
yes
id
f59c58cb-b76c-47ae-ae24-9b764e314f58
alternative location
https://eprint.iacr.org/2023/139
date added to LUP
2023-09-01 13:49:16
date last changed
2024-04-20 02:41:18
@inproceedings{f59c58cb-b76c-47ae-ae24-9b764e314f58,
  abstract     = {{In post-quantum cryptography (PQC), Learning With Errors (LWE) is one of the dominant underlying mathematical problems. For example, in NIST’s PQC standardization process, the Key Encapsulation Mechanism (KEM) protocol chosen for standardization was Kyber, an LWE-based scheme. Recently the dual attack surpassed the primal attack in terms of concrete complexity for solving the underlying LWE problem for multiple cryptographic schemes, including Kyber. The dual attack consists of a reduction part and a distinguishing part. When estimating the cost of the distinguishing part, one has to estimate the expected cost of enumerating over a certain number of positions of the secret key. Our contribution consists of giving a polynomial-time approach for calculating the expected complexity of such an enumeration procedure. This allows us to revise the complexity of the dual attack on the LWE-based protocols Kyber, Saber and TFHE. For all these schemes we improve upon the total bit-complexity in both the classical and the quantum setting.As our method of calculating the expected cost of enumeration is fairly general, it might be of independent interest in other areas of cryptography or even in other research areas.}},
  author       = {{Budroni, Alessandro and Mårtensson, Erik}},
  booktitle    = {{IEEE International Symposium on Information Theory (ISIT)}},
  isbn         = {{978-1-6654-7555-6}},
  language     = {{eng}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  title        = {{Improved Estimation of Key Enumeration with Applications to Solving LWE}},
  url          = {{http://dx.doi.org/10.1109/ISIT54713.2023.10206474}},
  doi          = {{10.1109/ISIT54713.2023.10206474}},
  year         = {{2023}},
}