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 introduce 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 or 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)-Learning with Errors and (Ring/Module)-Learning with Rounding 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 several candidates of the NIST post-quantum standardization process if sufficient oracle queries can be performed.

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

Date: received 9 Nov 2018, last revised 19 Nov 2018

Contact author: janpieter danvers at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Note: Added link to eprint

Version: 20181119:084710 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]