Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Guo, Qian LU and Mårtensson, Erik LU orcid (2023) The 14th International Conference on Post-Quantum Cryptography p.291-320
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... (More)
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. (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
The 14th International Conference on Post-Quantum Cryptography (PQCrypto 2023)
pages
30 pages
publisher
Springer
conference name
The 14th International Conference on Post-Quantum Cryptography
conference location
College Park, United States
conference dates
2023-08-16 - 2023-08-18
external identifiers
  • scopus:85172373550
ISBN
978-3-031-40002-5
978-3-031-40003-2
DOI
10.1007/978-3-031-40003-2_11
language
English
LU publication?
yes
id
93d60062-9710-4753-bce7-dc1a3d96e829
alternative location
https://eprint.iacr.org/2022/983
date added to LUP
2023-09-01 14:04:39
date last changed
2024-04-19 00:48:38
@inproceedings{93d60062-9710-4753-bce7-dc1a3d96e829,
  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.<br/>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.}},
  author       = {{Guo, Qian and Mårtensson, Erik}},
  booktitle    = {{The 14th International Conference on Post-Quantum Cryptography (PQCrypto 2023)}},
  isbn         = {{978-3-031-40002-5}},
  language     = {{eng}},
  pages        = {{291--320}},
  publisher    = {{Springer}},
  title        = {{Do Not Bound to a Single Position: Near-Optimal Multi-Positional Mismatch Attacks Against Kyber and Saber}},
  url          = {{http://dx.doi.org/10.1007/978-3-031-40003-2_11}},
  doi          = {{10.1007/978-3-031-40003-2_11}},
  year         = {{2023}},
}