Cryptology ePrint Archive: Report 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.

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

Date: received 22 Feb 2021

Contact author: janpieter danvers at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20210224:145327 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]