Paper 2024/897

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

Abstract

Laconic function evaluation (LFE) allows us to compress a circuit $$ into a short digest. Anybody can use this digest as a public-key to efficiently encrypt some input $$. Decrypting the resulting ciphertext reveals the output $$, while hiding everything else about $$. In this work we consider LFE for Random-Access Machines (RAM-LFE) where, instead of a circuit $$, we have a RAM program $$ that potentially contains some large hard-coded data $$. The decryption run-time to recover $$ from the ciphertext should be roughly the same as a plain evaluation of $$ in the RAM model, which can be sublinear in the size of $$. 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.