Paper 2019/1399

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

Jan-Pieter D'Anvers, 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 <X^N + 1> and demonstrate it on a simple Mod-LWE-based scheme parametrized à la Kyber768/Saber. We show that, using our technique, for a given secret key (single-target setting), the cost of searching for additional failing ciphertexts after one or more have already been found, can be sped up dramatically. We thus demonstrate that, in this single-target model, these schemes should be designed so that it is hard to even obtain one decryption failure. Besides, in a wider security model where there are many target secret keys (multi-target setting), our attack greatly improves over the state of the art.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in Eurocrypt 2020
Keywords
cryptanalysislattice-based cryptographyreaction attacksdecryption errors
Contact author(s)
janpieter danvers @ esat kuleuven be
melissa rossi @ ens fr
fernando virdia 2016 @ rhul ac uk
History
2020-02-12: last of 2 revisions
2019-12-04: received
See all versions
Short URL
https://ia.cr/2019/1399
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1399,
      author = {Jan-Pieter D'Anvers and Mélissa Rossi and Fernando Virdia},
      title = {(One) failure is not an option: Bootstrapping the search for failures in lattice-based encryption schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1399},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1399}},
      url = {https://eprint.iacr.org/2019/1399}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.