Paper 2021/193

Multitarget decryption failure attacks and their application to Saber and Kyber

Jan-Pieter D'Anvers and Senne Batsleer

Abstract

Many lattice-based encryption schemes are subject to a very small probability of decryption failures. It has been shown that an adversary can efficiently recover the secret key using a number of ciphertexts that cause such a decryption failure. In PKC~2019, D'Anvers~et~al. introduced `failure boosting', a technique to speed up the search for decryption failures. In this work we first improve the state-of-the-art multitarget failure boosting attacks. We then improve the cost calculation of failure boosting and extend the applicability of these calculations to permit cost calculations of real-world schemes. Using our newly developed methodologies we determine the multitarget decryption failure attack cost for all parameter sets of Saber and Kyber, showing among others that the quantum security of Saber can theoretically be reduced from 172 bits to 145 bits in specific circumstances. We then discuss the applicability of decryption failure attack in real-world scenarios, showing that an attack might not be practical to execute.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in Pkc 2022
Keywords
cryptanalysislattice-based cryptographyreaction attacksdecryption errors
Contact author(s)
janpieter danvers @ esat kuleuven be
History
2021-12-08: revised
2021-02-24: received
See all versions
Short URL
https://ia.cr/2021/193
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/193,
      author = {Jan-Pieter D'Anvers and Senne Batsleer},
      title = {Multitarget decryption failure attacks and their application to Saber and Kyber},
      howpublished = {Cryptology ePrint Archive, Paper 2021/193},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/193}},
      url = {https://eprint.iacr.org/2021/193}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.