Paper 2018/1089

On the impact of decryption failures on the security of LWE/LWR based schemes

Jan-Pieter D'Anvers, Frederik Vercauteren, and Ingrid Verbauwhede

Abstract

In this paper we investigate the impact of decryption failures on the chosen-ciphertext security of (Ring/Module)-Learning With Errors and (Ring/Module)-Learning with Rounding based primitives. Our analysis is split in three parts: First, we use a technique to increase the failure rate of these schemes called failure boosting. Based on this technique we investigate the minimal effort for an adversary to obtain a failure in 3 cases: when he has access to a quantum computer, when he mounts a multi-target attack and when he can only perform a limited number of oracle queries. Secondly, we examine the amount of information that an adversary can derive from failing ciphertexts. Finally, these techniques are combined in an attack on (Ring/Module)-LWE and (Ring/Module)-LWR based schemes with decryption failures. We provide both a theoretical analysis as well as an implementation to calculate the security impact and show that an attacker can significantly reduce the security of (Ring/Module)-LWE/LWR based schemes that have a relatively high failure rate. However, for the candidates of the NIST post-quantum standardization process that we assessed, the number of required oracle queries is above practical limits due to their conservative parameter choices.

Note: Added link to eprint

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2019
Keywords
Lattice cryptographyPost-quantum cryptographyDecryption failuresLWELWR
Contact author(s)
janpieter danvers @ esat kuleuven be
History
2019-01-28: last of 3 revisions
2018-11-09: received
See all versions
Short URL
https://ia.cr/2018/1089
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1089,
      author = {Jan-Pieter D'Anvers and Frederik Vercauteren and Ingrid Verbauwhede},
      title = {On the impact of decryption failures on the security of LWE/LWR based schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1089},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1089}},
      url = {https://eprint.iacr.org/2018/1089}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.