Welcome to the resource topic for 2025/1399
Title:
Tempo: ML-KEM to PAKE Compiler Resilient to Timing Attacks
Authors: Afonso Arriaga, Manuel Barbosa, Stanislaw Jarecki
Abstract:Recent KEM-to-PAKE compilers follow the Encrypted Key Exchange (EKE) paradigm (or a variant thereof), where the KEM public key is password-encrypted. While constant-time implementations of KEMs typically avoid secret-dependent branches and memory accesses, this requirement does not usually extend to operations involving the expansion of the public key because public keys are generally assumed to be public. A notable example is \mathsf{ML\textrm{-}KEM}, which expands a short seed \rho into a large matrix \mathsf{A} of polynomial coefficients using rejection sampling—a process that is variable-time but usually does not depend on any secret. However, in PAKE protocols that password-encrypt the compressed public key, this introduces the risk of timing honest parties and mounting an offline dictionary attack against the measurement. This is particularly concerning given the well-known real-world impact of such attacks on PAKE protocols.
In this paper we show two approaches which yield \mathsf{ML\textrm{-}KEM}-based PAKEs that resist timing attacks. First, we explore constant-time alternatives to \mathsf{ML\textrm{-}KEM} rejection sampling: one that refactors the original \mathsf{SampleNTT} algorithm into constant-time style code, whilst preserving its functionality, and two that modify the matrix expansion procedure to abandon rejection sampling and rely instead on large-integer modular arithmetic. All the proposed constant-time algorithms are slower than the current rejection sampling implementations, but they are still reasonably fast in absolute terms. Our conclusion is that adopting constant-time methods will imply both performance penalties and difficulties in using off-the-shelf \mathsf{ML\textrm{-}KEM} implementations. Alternatively, we present the first \mathsf{ML\textrm{-}KEM}-to-PAKE compiler that mitigates this issue by design: our proposal transmits the seed \rho in the clear, decoupling password-dependent runtime variations from the matrix expansion step. This means that vanilla implementations of \mathsf{ML\textrm{-}KEM} can be used as a black-box. Our new protocol \mathsf{Tempo} builds on the ideas from \mathsf{CHIC}, which considered splitting the KEM public key, adopts the two-round Feistel approach for password encryption of the non-expandable part of the public key, and leverages the proof techniques from \mathsf{NoIC} to show that, despite the malleability permitted by the two-round Feistel, it is sufficient for password extraction and protocol simulation in the UC framework.
ePrint: https://eprint.iacr.org/2025/1399
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .