International Association
for Cryptologic Research

Laconic function evaluation (LFE) is a ``flipped'' version of fully homomorphic encryption, where the server performing the computation gets the output. The server commits itself to a function $f$ by outputting a small digest. Clients can later efficiently encrypt inputs $x$ with respect to the digest in much less time than computing $f$, and ensure that the server only decrypts $f(x)$, but does not learn anything else about $x$. Prior works constructed LFE for \emph{circuits} under LWE, and for \emph{Turing Machines (TMs)} from indistinguishability obfuscation (iO). In this work we introduce LFE for \emph{Random-Access Machines} (RAM-LFE). The server commits itself to a potentially huge database $y$ via a short digest. Clients can later efficiently encrypt inputs $x$ with respect to the digest and the server decrypts $f(x,y)$ for some specified RAM program $f$ (e.g., a universal RAM), without learning anything else about $x$. The main advantage of RAM-LFE is that the server's decryption run-time only scales with the RAM run-time $T$ of the computation $f(x,y)$, which can be sublinear in both $|x|$ and $|y|$. We consider a \emph{weakly efficient} variant, where the client's run-time is also allowed to scale linearly with $T$, but not $|y|$, and a \emph{strongly efficient} variant, where the client's run-time must be sublinear in both $T$ and $|y|$. We construct the the former from doubly efficient private information retrieval (DEPIR) and laconic OT (LOT), both of which are known from RingLWE, and the latter from an additional use of iO. We then show how to leverage strongly efficient RAM-LFE to also get (many-key) \emph{functional encryption for RAMs (RAM-FE)} where secret keys are associate with big databases $y$ and the decryption time is sublinear in $|y|$, as well as \emph{iO for RAMs} where the obfuscated program contains a big database $y$ and the evaluation time is sublinear in $|y|$.

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.

Cryptography often considers the strongest yet plausible attacks in the real world. Preprocessing (a.k.a. non-uniform attacks) plays an important role in both theory and practice: an efficient online attacker can take advantage of advice prepared by a time-consuming preprocessing stage. Salting is a heuristic strategy to counter preprocessing attacks by feeding a small amount of randomness to the cryptographic primitive. We present general and tight characterizations of preprocessing against cryptographic salting, with upper bounds matching the advantages of the most intuitive attack. Our result quantitatively strengthens the previous work by Coretti, Dodis, Guo, and Steinberger (EUROCRYPT'18). Our proof exploits a novel connection between the non-uniform security of salted games and direct product theorems for memoryless algorithms. For quantum adversaries, we give similar characterizations for property finding games, resolving an open problem of the quantum non-uniform security of salted collision resistant hash by Chung, Guo, Liu, and Qian (FOCS'20). Our proof extends the compressed oracle framework of Zhandry (CRYPTO'19) to prove quantum strong direct product theorems for property finding games in the average-case hardness.