Cryptology ePrint Archive: Report 2018/1089

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

Jan-Pieter D'Anvers and 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.

Category / Keywords: public-key cryptography / Lattice cryptography, Post-quantum cryptography, Decryption failures, LWE/LWR

Original Publication (with major differences): IACR-PKC-2019

Date: received 9 Nov 2018, last revised 28 Jan 2019

Contact author: janpieter danvers at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Note: Added link to eprint

Version: 20190128:091738 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]