Do Not Bound to a Single Position: Near-Optimal Multi-Positional Mismatch Attacks Against Kyber and Saber
(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:
https://lup.lub.lu.se/record/93d60062-9710-4753-bce7-dc1a3d96e829
- author
- Guo, Qian LU and Mårtensson, Erik LU
- organization
- publishing date
- 2023
- 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-40003-2
- 978-3-031-40002-5
- 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-09-06 14:06:14
@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-40003-2}}, 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}}, }