Do Not Bound to a Single Position: Near-Optimal Multi-Positional Mismatch Attacks Against Kyber and Saber

Qian Guo; Erik Mårtensson

Paper 2022/983

Do Not Bound to a Single Position: Near-Optimal Multi-Positional Mismatch Attacks Against Kyber and Saber

Qian Guo

, Lund University

Erik Mårtensson

, University of Bergen, Lund University

Abstract

Misuse resilience is an important security criterion in the evaluation of the NIST Post-quantum cryptography standardization process. In this paper, we propose new key mismatch attacks against Kyber and Saber, NIST's selected scheme for encryption and one of the finalists in the third round of the NIST competition, respectively. Our novel idea is to recover partial information of multiple secret entries in each mismatch oracle call. These multi-positional attacks greatly reduce the expected number of oracle calls needed to fully recover the secret key. They also have significance in side-channel analysis. From the perspective of lower bounds, our new attacks falsify the Huffman bounds proposed in [Qin et al. ASIACRYPT 2021], where a one- positional mismatch adversary is assumed. Our new attacks can be bounded by the Shannon lower bounds, i.e., the entropy of the distribution generating each secret coefficient times the number of secret entries. We call the new attacks "near-optimal" since their query complexities are close to the Shannon lower bounds.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Lattice-based cryptography Mismatch attacks LWE LWR Kyber Saber
Contact author(s): qian guo @ eit lth se
erik martensson @ uib no
History: 2022-08-03: approved; 2022-08-01: received; See all versions
Short URL: https://ia.cr/2022/983
License: CC BY

BibTeX

@misc{cryptoeprint:2022/983,
      author = {Qian Guo and Erik Mårtensson},
      title = {Do Not Bound to a Single Position: Near-Optimal Multi-Positional Mismatch Attacks Against Kyber and Saber},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/983},
      year = {2022},
      url = {https://eprint.iacr.org/2022/983}
}