CryptoDB
Key-Homomorphic Computations for RAM: Fully Succinct Randomised Encodings and More
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| 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 \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\poly(\log T, \log L)$ and rate-1 encodings. 3. Key-policy attribute-based encryption for RAM programs, with ciphertexts of size $\poly(T)$. The same scheme can be converted to the \emph{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). |
BibTeX
@inproceedings{crypto-2025-35637,
title={Key-Homomorphic Computations for RAM: Fully Succinct Randomised Encodings and More},
publisher={Springer-Verlag},
author={Damiano Abram and Giulio Malavolta and Lawrence Roy},
year=2025
}