Paper 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.
Note: Added link to eprint
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- 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
-
CC BY