Paper 2026/2715

A Constant-Rate Compiler for Continual Memory Leakage

Abstract

Leakage-resilient compilers transform any computation so that physical leakage from its implementation reveals nothing beyond its input-output behaviour. In this work, we investigate this question in the well-motivated continual memory leakage (CML) model, that captures a variety of relevant real-world side-channel attacks and subsumes several other well studied models in the leakage domain. In this model with two independently leaking components (at least two are necessary), all known general compilers tolerate only an inverse-polynomial leakage-rate. We give a compiler with constant leakage-rate, in the hybrid model with a simple inputless leak-free sampler as in Dziembowski and Faust (TCC 2012). It protects any deterministic computation on a fixed secret with public inputs and outputs, and comes with a transfer theorem: any security game in which the adversary has an oracle for the computation remains secure when every oracle call is replaced by a compiled evaluation that leaks continuously. Our compiler uses no computational assumption. Our main application is public-key encryption. Applied to the decryption of any IND-CCA2 secure PKE, the compiler gives IND-CCLA2 security, i.e. CCA2 security even when every decryption leaks, including after the challenge ciphertext, with the same public key, ciphertexts and encryption algorithm. Instantiating the base scheme gives such PKE from LWE and from LPN improving upon the previous best post-quantum constructions in this model, which supported only inverse-polynomial leakage-rate. We also obtain signatures, PRFs and MACs with constant leakage-rate via a natural generalization. Our key idea is to pack the entire configuration of a universal machine into one element of a large extension field, so that any computation keeps only a constant number of inner-product encodings in memory at any time, each for only a constant number of rounds. Our techniques are inspired by packing techniques in homomorphic encryption adapted to a completely different context. We are optimistic that our techniques will find other applications.

Note: To be submitted.