Paper 2021/193

Multitarget decryption failure attacks and their application to Saber and Kyber

Jan-Pieter D'Anvers and Senne Batsleer


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.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in Pkc 2022
cryptanalysislattice-based cryptographyreaction attacksdecryption errors
Contact author(s)
janpieter danvers @ esat kuleuven be
2021-12-08: revised
2021-02-24: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.