What a lovely hat

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 $(|\mathbf{x}| + |\mathbf{y}|)\cdot \text{poly}(\log T, \log L)$ and rate-1 encodings. 2) Laconic function evaluation for RAM programs, with encoder runtime bounded by $(|\mathbf{x}| + |\mathbf{y}|)\cdot\text{poly}(\log T, \log L)$ and rate-1 encodings. 3) Key-policy attribute-based encryption for RAM programs, with ciphertexts of size $O(T)$. 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).