Paper 2023/098

Belief Propagation Meets Lattice Reduction: Security Estimates for Error-Tolerant Key Recovery from Decryption Errors

Julius Hermelink, Max Planck Institute for Security and Privacy
Erik Mårtensson, University of Bergen, Lund University
Simona Samardjiska, Radboud University Nijmegen
Peter Pessl, Infineon Technologies (Germany)
Gabi Dreo Rodosek, Bundeswehr University Munich

In LWE-based KEMs, observed decryption errors leak information about the secret key in the form of equations or inequalities. Several practical fault attacks have already exploited such leakage by either directly applying a fault or enabling a chosen-ciphertext attack using a fault. When the leaked information is in the form of inequalities, the recovery of the secret key is not trivial. Recent methods use either statistical or algebraic methods (but not both), with some being able to handle incorrect information. Having in mind that integration of the side-channel information is a crucial part of several classes of implementation attacks on LWE-based schemes, it is an important question whether statistically processed information can be successfully integrated in lattice reduction algorithms. We answer this question positively by proposing an error-tolerant combination of statistical and algebraic methods that make use of the advantages of both approaches. The combination enables us to improve upon existing methods -- we use both fewer inequalities and are more resistant to errors. We further provide precise security estimates based on the number of available inequalities. Our recovery method applies to several types of implementation attacks in which decryption errors are used in a chosen-ciphertext attack. We practically demonstrate the improved performance of our approach in a key-recovery attack against Kyber with fault-induced decryption errors.

Available format(s)
Attacks and cryptanalysis
Publication info
Published by the IACR in TCHES 2023
KyberLWEBelief PropagationLattice ReductionSVPImplementation Attack
Contact author(s)
julius hermelink @ mpi-sp org
erik martensson @ uib no
simonas @ cs ru nl
peter pessl @ infineon com
gabi dreo @ unibw de
2023-07-12: last of 2 revisions
2023-01-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Julius Hermelink and Erik Mårtensson and Simona Samardjiska and Peter Pessl and Gabi Dreo Rodosek},
      title = {Belief Propagation Meets Lattice Reduction: Security Estimates for Error-Tolerant Key Recovery from Decryption Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2023/098},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.