A novel CCA attack using decryption errors against LAC
Guo, Qian LU ; Johansson, Thomas LU
and Yang, Jing
LU
(2019)
25th International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
11921 LNCS.
p.82-111
- Abstract
Cryptosystems based on Learning with Errors or related problems are central topics in recent cryptographic research. One main witness to this is the NIST Post-Quantum Cryptography Standardization effort. Many submitted proposals rely on problems related to Learning with Errors. Such schemes often include the possibility of decryption errors with some very small probability. Some of them have a somewhat larger error probability in each coordinate, but use an error correcting code to get rid of errors. In this paper we propose and discuss an attack for secret key recovery based on generating decryption errors, for schemes using error correcting codes. In particular we show an attack on the scheme LAC, a proposal to the NIST Post-Quantum... (More)
Cryptosystems based on Learning with Errors or related problems are central topics in recent cryptographic research. One main witness to this is the NIST Post-Quantum Cryptography Standardization effort. Many submitted proposals rely on problems related to Learning with Errors. Such schemes often include the possibility of decryption errors with some very small probability. Some of them have a somewhat larger error probability in each coordinate, but use an error correcting code to get rid of errors. In this paper we propose and discuss an attack for secret key recovery based on generating decryption errors, for schemes using error correcting codes. In particular we show an attack on the scheme LAC, a proposal to the NIST Post-Quantum Cryptography Standardization that has advanced to round 2. In a standard setting with CCA security, the attack first consists of a precomputation of special messages and their corresponding error vectors. This set of messages are submitted for decryption and a few decryption errors are observed. In a statistical analysis step, these vectors causing the decryption errors are processed and the result reveals the secret key. The attack only works for a fraction of the secret keys. To be specific, regarding LAC256, the version for achieving the 256-bit classical security level, we recover one key among approximately 264 public keys with complexity 279, if the precomputation cost of 2162 is excluded. We also show the possibility to attack a more probable key (say with probability 2-16). This attack is verified via extensive simulation. We further apply this attack to LAC256-v2, a new version of LAC256 in round 2 of the NIST PQ-project and obtain a multi-target attack with slightly increased precomputation complexity (from 2162 to 2171). One can also explain this attack in the single-key setting as an attack with precomputation complexity of 2171 and success probability of 2-64.
(Less)
- author
- Guo, Qian
LU
; Johansson, Thomas
LU
and Yang, Jing
LU
- organization
- publishing date
- 2019-11-25
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Chosen-ciphertext security, Decryption errors, LAC, Lattice-based cryptography, LWE, NIST post-quantum standardization, Reaction attack
- host publication
- Advances in Cryptology – ASIACRYPT 2019 : 25th International Conference on the Theory and Application of Cryptology and Information Security, 2019, Proceedings, Part I - 25th International Conference on the Theory and Application of Cryptology and Information Security, 2019, Proceedings, Part I
- series title
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
- editor
- Galbraith, Steven D. and Moriai, Shiho
- volume
- 11921 LNCS
- pages
- 30 pages
- publisher
- Springer Gabler
- conference name
- 25th International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
- conference location
- Kobe, Japan
- conference dates
- 2019-12-08 - 2019-12-12
- external identifiers
-
- scopus:85076699464
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 9783030345778
- 978-3-030-34578-5
- DOI
- 10.1007/978-3-030-34578-5_4
- language
- English
- LU publication?
- yes
- id
- a2330486-01df-44fb-a22a-8908cdc58d0a
- date added to LUP
- 2020-01-10 11:36:26
- date last changed
- 2024-05-15 04:28:47
@inproceedings{a2330486-01df-44fb-a22a-8908cdc58d0a,
abstract = {{<p>Cryptosystems based on Learning with Errors or related problems are central topics in recent cryptographic research. One main witness to this is the NIST Post-Quantum Cryptography Standardization effort. Many submitted proposals rely on problems related to Learning with Errors. Such schemes often include the possibility of decryption errors with some very small probability. Some of them have a somewhat larger error probability in each coordinate, but use an error correcting code to get rid of errors. In this paper we propose and discuss an attack for secret key recovery based on generating decryption errors, for schemes using error correcting codes. In particular we show an attack on the scheme LAC, a proposal to the NIST Post-Quantum Cryptography Standardization that has advanced to round 2. In a standard setting with CCA security, the attack first consists of a precomputation of special messages and their corresponding error vectors. This set of messages are submitted for decryption and a few decryption errors are observed. In a statistical analysis step, these vectors causing the decryption errors are processed and the result reveals the secret key. The attack only works for a fraction of the secret keys. To be specific, regarding LAC256, the version for achieving the 256-bit classical security level, we recover one key among approximately 2<sup>64</sup> public keys with complexity 2<sup>79</sup>, if the precomputation cost of 2<sup>162</sup> is excluded. We also show the possibility to attack a more probable key (say with probability 2<sup>-16</sup>). This attack is verified via extensive simulation. We further apply this attack to LAC256-v2, a new version of LAC256 in round 2 of the NIST PQ-project and obtain a multi-target attack with slightly increased precomputation complexity (from 2<sup>162</sup> to 2<sup>171</sup>). One can also explain this attack in the single-key setting as an attack with precomputation complexity of 2<sup>171</sup> and success probability of 2<sup>-64</sup>.</p>}},
author = {{Guo, Qian and Johansson, Thomas and Yang, Jing}},
booktitle = {{Advances in Cryptology – ASIACRYPT 2019 : 25th International Conference on the Theory and Application of Cryptology and Information Security, 2019, Proceedings, Part I}},
editor = {{Galbraith, Steven D. and Moriai, Shiho}},
isbn = {{9783030345778}},
issn = {{1611-3349}},
keywords = {{Chosen-ciphertext security; Decryption errors; LAC; Lattice-based cryptography; LWE; NIST post-quantum standardization; Reaction attack}},
language = {{eng}},
month = {{11}},
pages = {{82--111}},
publisher = {{Springer Gabler}},
series = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}},
title = {{A novel CCA attack using decryption errors against LAC}},
url = {{http://dx.doi.org/10.1007/978-3-030-34578-5_4}},
doi = {{10.1007/978-3-030-34578-5_4}},
volume = {{11921 LNCS}},
year = {{2019}},
}