Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A Generic Framework for Side-Channel Attacks Against LWE-Based Cryptosystems

Hermelink, Julius ; Streit, Silvan ; Mårtensson, Erik LU orcid and Petri, Richard (2025) 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025 In Lecture Notes in Computer Science 15608. p.3-32
Abstract

Lattice-based cryptography is in the process of being standardized. Several proposals to deal with side-channel information using lattice reduction exist. However, it has been shown that algorithms based on Bayesian updating are often more favorable in practice. In this work, we define distribution hints; a type of hint that allows modelling probabilistic information. These hints generalize most previously defined hints and the information obtained in several attacks. We define two solvers for our hints; one is based on belief propagation and the other one uses a greedy approach. We prove that the latter is a computationally less expensive approximation of the former and that previous algorithms used for specific attacks may be seen as... (More)

Lattice-based cryptography is in the process of being standardized. Several proposals to deal with side-channel information using lattice reduction exist. However, it has been shown that algorithms based on Bayesian updating are often more favorable in practice. In this work, we define distribution hints; a type of hint that allows modelling probabilistic information. These hints generalize most previously defined hints and the information obtained in several attacks. We define two solvers for our hints; one is based on belief propagation and the other one uses a greedy approach. We prove that the latter is a computationally less expensive approximation of the former and that previous algorithms used for specific attacks may be seen as special cases of our solvers. Thereby, we provide a systematization of previously obtained information and used algorithms in real-world side-channel attacks. In contrast to lattice-based approaches, our framework is not limited to value leakage. For example, it can deal with noisy Hamming weight leakage or partially incorrect information. Moreover, it improves upon the recovery of the secret key from approximate hints in the form they arise in real-world attacks. Our framework has several practical applications: We exemplarily show that a recent attack can be improved; we reduce the number of traces and corresponding ciphertexts and increase the noise resistance. Further, we explain how distribution hints could be applied in the context of previous attacks and outline a potential new attack.

(Less)
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Belief Propagation, Kyber, Lattice Reduction, Lattice-based cryptography, ML-KEM, Side-Channel Attacks
host publication
Advances in Cryptology – EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2025, Proceedings
series title
Lecture Notes in Computer Science
editor
Fehr, Serge and Fouque, Pierre-Alain
volume
15608
pages
30 pages
publisher
Springer Science and Business Media B.V.
conference name
44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025
conference location
Madrid, Spain
conference dates
2025-05-04 - 2025-05-08
external identifiers
  • scopus:105004789474
ISSN
1611-3349
0302-9743
ISBN
9783031911002
DOI
10.1007/978-3-031-91101-9_1
language
English
LU publication?
yes
id
6417b785-bc11-438c-b8c3-5cbeeab477c2
date added to LUP
2025-09-16 14:05:11
date last changed
2025-09-30 15:46:33
@inproceedings{6417b785-bc11-438c-b8c3-5cbeeab477c2,
  abstract     = {{<p>Lattice-based cryptography is in the process of being standardized. Several proposals to deal with side-channel information using lattice reduction exist. However, it has been shown that algorithms based on Bayesian updating are often more favorable in practice. In this work, we define distribution hints; a type of hint that allows modelling probabilistic information. These hints generalize most previously defined hints and the information obtained in several attacks. We define two solvers for our hints; one is based on belief propagation and the other one uses a greedy approach. We prove that the latter is a computationally less expensive approximation of the former and that previous algorithms used for specific attacks may be seen as special cases of our solvers. Thereby, we provide a systematization of previously obtained information and used algorithms in real-world side-channel attacks. In contrast to lattice-based approaches, our framework is not limited to value leakage. For example, it can deal with noisy Hamming weight leakage or partially incorrect information. Moreover, it improves upon the recovery of the secret key from approximate hints in the form they arise in real-world attacks. Our framework has several practical applications: We exemplarily show that a recent attack can be improved; we reduce the number of traces and corresponding ciphertexts and increase the noise resistance. Further, we explain how distribution hints could be applied in the context of previous attacks and outline a potential new attack.</p>}},
  author       = {{Hermelink, Julius and Streit, Silvan and Mårtensson, Erik and Petri, Richard}},
  booktitle    = {{Advances in Cryptology – EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2025, Proceedings}},
  editor       = {{Fehr, Serge and Fouque, Pierre-Alain}},
  isbn         = {{9783031911002}},
  issn         = {{1611-3349}},
  keywords     = {{Belief Propagation; Kyber; Lattice Reduction; Lattice-based cryptography; ML-KEM; Side-Channel Attacks}},
  language     = {{eng}},
  pages        = {{3--32}},
  publisher    = {{Springer Science and Business Media B.V.}},
  series       = {{Lecture Notes in Computer Science}},
  title        = {{A Generic Framework for Side-Channel Attacks Against LWE-Based Cryptosystems}},
  url          = {{http://dx.doi.org/10.1007/978-3-031-91101-9_1}},
  doi          = {{10.1007/978-3-031-91101-9_1}},
  volume       = {{15608}},
  year         = {{2025}},
}