Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Hermelink, Julius ; Mårtensson, Erik LU orcid ; Samardjiska, Simona ; Pessl, Peter and Dreo Rodosek, Gabi (2023) In IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES) 2023(4).
Abstract
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 LWEbased schemes, it is an important question whether statistically processed information can be... (More)
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 LWEbased 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. (Less)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES)
volume
2023
issue
4
publisher
Ruhr-University of Bochum
external identifiers
  • scopus:85170208357
ISSN
2569-2925
DOI
10.46586/tches.v2023.i4.287-317
language
English
LU publication?
yes
id
e9fa821b-2e7b-44f3-aec3-616dc8e5cc1a
alternative location
https://eprint.iacr.org/2023/098
date added to LUP
2023-09-01 14:21:38
date last changed
2024-02-18 19:13:36
@article{e9fa821b-2e7b-44f3-aec3-616dc8e5cc1a,
  abstract     = {{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 LWEbased schemes, it is an important question whether statistically processed information can be successfully integrated in lattice reduction algorithms.<br/>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.<br/>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.}},
  author       = {{Hermelink, Julius and Mårtensson, Erik and Samardjiska, Simona and Pessl, Peter and Dreo Rodosek, Gabi}},
  issn         = {{2569-2925}},
  language     = {{eng}},
  number       = {{4}},
  publisher    = {{Ruhr-University of Bochum}},
  series       = {{IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES)}},
  title        = {{Belief Propagation Meets Lattice Reduction: Security Estimates for Error-Tolerant Key Recovery from Decryption Errors}},
  url          = {{http://dx.doi.org/10.46586/tches.v2023.i4.287-317}},
  doi          = {{10.46586/tches.v2023.i4.287-317}},
  volume       = {{2023}},
  year         = {{2023}},
}