Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Further improvements of the estimation of key enumeration with applications to solving LWE

Budroni, Alessandro LU and Mårtensson, Erik LU orcid (2024) In Cryptography and Communications
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. The primal and the dual attacks are the two main strategies considered for solving the underlying LWE problem of multiple cryptographic schemes, including Kyber. Recently, the dual attack gathered significant attention within the research community. A series of studies initially suggested that it might be more efficient than the primal attack. Then, a subsequent work by Ducas and Pulles (Crypto'23) raised doubts on the estimated complexity of such an approach. The... (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. The primal and the dual attacks are the two main strategies considered for solving the underlying LWE problem of multiple cryptographic schemes, including Kyber. Recently, the dual attack gathered significant attention within the research community. A series of studies initially suggested that it might be more efficient than the primal attack. Then, a subsequent work by Ducas and Pulles (Crypto'23) raised doubts on the estimated complexity of such an approach. The 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.

Previous works dealt with this problem either using unexplained models for estimating the cost of enumeration or by using unnecessarily pessimistic upper limit formulas. Our contribution consists of giving a polynomial-time approach for calculating the expected complexity of such an enumeration procedure. This allows us to decrease the estimated cost of this procedure and, hence, of the whole attack both classically and quantumly. In addition, we explore different enumeration strategies to achieve some further improvements. Our work is independent from the questions raised by Ducas and Pulles which do not concern the estimation of the enumeration procedure in the dual attack.

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
Contribution to journal
publication status
epub
subject
in
Cryptography and Communications
publisher
Springer
external identifiers
  • scopus:85195855900
ISSN
1936-2455
DOI
10.1007/s12095-024-00722-1
language
English
LU publication?
yes
id
b5831bdf-9f7f-475a-bd5c-c22a2bdd81aa
date added to LUP
2024-06-19 15:13:22
date last changed
2024-06-20 11:41:24
@article{b5831bdf-9f7f-475a-bd5c-c22a2bdd81aa,
  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.  The primal and the dual attacks are the two main strategies considered for solving the underlying LWE problem of multiple cryptographic schemes, including Kyber. Recently, the dual attack gathered significant attention within the research community. A series of studies initially suggested that it might be more efficient than the primal attack. Then, a subsequent work by Ducas and Pulles (Crypto'23) raised doubts on the estimated complexity of such an approach. The 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.<br/><br/>Previous works dealt with this problem either using unexplained models for estimating the cost of enumeration or by using unnecessarily pessimistic upper limit formulas. Our contribution consists of giving a polynomial-time approach for calculating the expected complexity of such an enumeration procedure. This allows us to decrease the estimated cost of this procedure and, hence, of the whole attack both classically and quantumly. In addition, we explore different enumeration strategies to achieve some further improvements. Our work is independent from the questions raised by Ducas and Pulles which do not concern the estimation of the enumeration procedure in the dual attack. <br/><br/>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}},
  issn         = {{1936-2455}},
  language     = {{eng}},
  month        = {{06}},
  publisher    = {{Springer}},
  series       = {{Cryptography and Communications}},
  title        = {{Further improvements of the estimation of key enumeration with applications to solving LWE}},
  url          = {{http://dx.doi.org/10.1007/s12095-024-00722-1}},
  doi          = {{10.1007/s12095-024-00722-1}},
  year         = {{2024}},
}