[Resource Topic] 2024/897: Laconic Function Evaluation and ABE for RAMs from (Ring-)LWE

Welcome to the resource topic for 2024/897

Laconic Function Evaluation and ABE for RAMs from (Ring-)LWE

Authors: Fangqi Dong, Zihan Hao, Ethan Mook, Hoeteck Wee, Daniel Wichs


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 Random-Access Machines (RAM-LFE) where, instead of a circuit f, we have a RAM program f_{\mathsf{DB}} that potentially contains some large hard-coded data \mathsf{DB}. The decryption run-time to recover f_{\mathsf{DB}}(x) from the ciphertext should be roughly the same as a plain evaluation of f_{\mathsf{DB}}(x) in the RAM model, which can be sublinear in the size of \mathsf{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 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 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 attribute-based encryption for RAMs (RAM-ABE), from LWE.

ePrint: https://eprint.iacr.org/2024/897

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .