International Association
for Cryptologic Research

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.