Paper 2025/339

Key-Homomorphic Computations for RAM: Fully Succinct Randomised Encodings and More

Abstract

We propose a new method to construct a public-key encryption scheme, where one can homomorphically transform a ciphertext encrypted under a key $\mathbf{x}$ into a ciphertext under $(P,P(\mathbf{x}))$, for any polynomial-time RAM program $P:\mathbf{x}\mapsto \mathbf{y}$ with runtime $T$ and memory $L$. Combined with other lattice techniques, this allows us to construct: 1) Succinct-randomised encodings from RAM programs with encoder complexity $$ and rate-1 encodings. 2) Laconic function evaluation for RAM programs, with encoder runtime bounded by $$ and rate-1 encodings. 3) Key-policy attribute-based encryption for RAM programs, with ciphertexts of size $$. The same scheme can be converted to the register setting, obtaining linear CRS size in the number of parties. All of our schemes rely on the hardness of the \emph{decomposed learning with errors} (LWE) problem, along with other standard computational assumptions on lattices. The decomposed LWE problem can be interpreted as postulating the circular-security of a natural lattice-based public-key encryption scheme. To gain confidence in the assumption, we show that it is implied by the hardness of the succinct LWE problem of Wee (CRYPTO'24).