Cryptology ePrint Archive: Report 2019/1399

(One) failure is not an option: Bootstrapping the search for failures in lattice-based encryption schemes

Jan-Pieter D'Anvers and Mélissa Rossi and Fernando Virdia

Abstract: Lattice-based encryption schemes are often subject to the possibility of decryption failures, in which valid encryptions are decrypted incorrectly. Such failures, in large number, leak information about the secret key, enabling an attack strategy alternative to pure lattice reduction. Extending the failure boosting technique of D'Anvers et al. in PKC 2019, we propose an approach that we call directional failure boosting that uses previously found failing ciphertexts to accelerate the search for new ones. We analyse in detail the case where the lattice is defined over polynomial ring modules quotiented by $\langle X^{N} + 1 \rangle$ and demonstrate it on a simple Mod-LWE-based scheme parametrized à la Kyber768/Saber. We show that using our technique, the cost of searching for additional failing ciphertexts after one or more have already been found can be sped up dramatically, thus demonstrating that these schemes should be designed so that it is hard to even obtain one decryption failure.

Category / Keywords: public-key cryptography / cryptanalysis, lattice-based cryptography, reaction attacks, decryption errors

Date: received 3 Dec 2019, last revised 4 Dec 2019

Contact author: janpieter danvers at esat kuleuven be,melissa rossi@ens fr,fernando virdia 2016@rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20191204:135346 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]