Paper 2019/1308

A Novel CCA Attack using Decryption Errors against LAC

Qian Guo, Thomas Johansson, and Jing Yang

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 {\sf 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 {\sf LAC}256, 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 {\sf LAC}256-v2, a new version of {\sf LAC}256 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}\).