[Resource Topic] 2018/1089: On the impact of decryption failures on the security of LWE/LWR based schemes

Welcome to the resource topic for 2018/1089

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

Authors: Jan-Pieter D'Anvers, Frederik Vercauteren, Ingrid Verbauwhede


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.

ePrint: https://eprint.iacr.org/2018/1089

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .