International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: A Novel CCA Attack Using Decryption Errors Against LAC

Authors:
Qian Guo
Thomas Johansson
Jing Yang
Download:
DOI: 10.1007/978-3-030-34578-5_4
Search ePrint
Search Google
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 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^{64}$$ public keys with complexity $$2^{79}$$, if the precomputation cost of $$2^{162}$$ 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 $$2^{162}$$ to $$2^{171}$$). One can also explain this attack in the single-key setting as an attack with precomputation complexity of $$2^{171}$$ and success probability of $$2^{-64}$$.
BibTeX
@article{asiacrypt-2019-30011,
  title={A Novel CCA Attack Using Decryption Errors Against LAC},
  booktitle={Advances in Cryptology – ASIACRYPT 2019},
  series={Advances in Cryptology – ASIACRYPT 2019},
  publisher={Springer},
  volume={11921},
  pages={82-111},
  doi={10.1007/978-3-030-34578-5_4},
  author={Qian Guo and Thomas Johansson and Jing Yang},
  year=2019
}