A novel CCA attack using decryption errors against LAC

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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 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.

Details

Authors
Organisations
External organisations
  • University of Bergen
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Signal Processing
  • Computational Mathematics

Keywords

  • Chosen-ciphertext security, Decryption errors, LAC, Lattice-based cryptography, LWE, NIST post-quantum standardization, Reaction attack
Original languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2019
Subtitle of host publication25th International Conference on the Theory and Application of Cryptology and Information Security, 2019, Proceedings, Part I
EditorsSteven D. Galbraith, Shiho Moriai
PublisherSpringer Gabler
Pages82-111
Number of pages30
ISBN (Electronic)978-3-030-34578-5
ISBN (Print)9783030345778
Publication statusPublished - 2019 Nov 25
Publication categoryResearch
Peer-reviewedYes
Event25th International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019 - Kobe, Japan
Duration: 2019 Dec 82019 Dec 12

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11921 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
CountryJapan
CityKobe
Period2019/12/082019/12/12