Paper 2024/068

Laconic Function Evaluation, Functional Encryption and Obfuscation for RAMs with Sublinear Computation

Fangqi Dong, Tsinghua University
Zihan Hao, Tsinghua University
Ethan Mook, Northeastern University
Daniel Wichs, Northeastern University, NTT Research
Abstract

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 circuits under LWE, and for Turing Machines (TMs) from indistinguishability obfuscation (iO). In this work we introduce LFE for 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 weakly efficient variant, where the client's run-time is also allowed to scale linearly with $T$, but not $|y|$, and a fully efficient variant, where the client's run-time must be sublinear in both $T$ and $|y|$. We construct 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 fully efficient RAM-LFE to also get (many-key) 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 iO for RAMs where the obfuscated program contains a big database $y$ and the evaluation time is sublinear in $|y|$.

Note: Add citation

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2024
DOI
10.1007/978-3-031-58723-8_7
Keywords
laconic function evaluationfunctional encryptionindistinguishability obfuscation
Contact author(s)
dfq20 @ mails tsinghua edu cn
haozh20 @ mails tsinghua edu cn
mook e @ northeastern edu
wichs @ ccs neu edu
History
2024-06-05: revised
2024-01-16: received
See all versions
Short URL
https://ia.cr/2024/068
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/068,
      author = {Fangqi Dong and Zihan Hao and Ethan Mook and Daniel Wichs},
      title = {Laconic Function Evaluation, Functional Encryption and Obfuscation for {RAMs} with Sublinear Computation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/068},
      year = {2024},
      doi = {10.1007/978-3-031-58723-8_7},
      url = {https://eprint.iacr.org/2024/068}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.