International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Damiano Abram , Bocconi University
Giulio Malavolta , Bocconi University
Lawrence Roy , Aarhus University
Download:
Search ePrint
Search Google
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
}