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

##### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2022/983

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},
note = {\url{https://eprint.iacr.org/2022/983}},
url = {https://eprint.iacr.org/2022/983}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.