CryptoDB
Laconic Function Evaluation and ABE for RAMs from (Ring-)LWE
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2024 |
| Abstract: | Laconic function evaluation (LFE) allows us to compress a circuit $f$ into a short digest. Anybody can use this digest as a public-key to efficiently encrypt some input $x$. Decrypting the resulting ciphertext reveals the output $f(x)$, while hiding everything else about $x$. In this work we consider LFE for \emph{Random-Access Machines} (RAM-LFE) where, instead of a circuit $f$, we have a RAM program $f_{\DB}$ that potentially contains some large hard-coded data $\DB$. The decryption run-time to recover $f_{\DB}(x)$ from the ciphertext should be roughly the same as a plain evaluation of $f_{\DB}(x)$ in the RAM model, which can be sublinear in the size of $\DB$. Prior works constructed LFE for circuits under LWE, and RAM-LFE under indisitinguishability obfuscation (iO) and Ring-LWE. In this work, we construct RAM-LFE with essentially optimal encryption and decryption run-times from just Ring-LWE and a standard circular security assumption, without iO. RAM-LFE directly yields 1-key succinct functional encryption and reusable garbling for RAMs with similar parameters. If we only want an \emph{attribute-based} LFE for RAMs (RAM-AB-LFE), then we can replace Ring-LWE with plain LWE in the above. Orthogonally, if we only want \emph{leveled} schemes, where the encryption/decryption efficiency can scale with the depth of the RAM computation, then we can remove the need for a circular-security. Lastly, we also get a leveled many-key \emph{attribute-based encryption for RAMs (RAM-ABE)}, from LWE. |
BibTeX
@inproceedings{crypto-2024-34199,
title={Laconic Function Evaluation and ABE for RAMs from (Ring-)LWE},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-68382-4_4},
author={Fangqi Dong and Zihan Hao and Ethan Mook and Hoeteck Wee and Daniel Wichs},
year=2024
}