Now, three researchers have crafted a long-sought version of private information retrieval and extended it to build a more general privacy strategy. The work, which received a Best Paper Award in June at the annual Symposium on Theory of Computing, topples a major theoretical barrier on the way to a truly private search.
https://eprint.iacr.org/2022/1703 <noscript> <h1 class="text-center">What a lovely hat</h1> <h4 class="text-center">Is it made out of <a href="https://iacr.org/tinfoil.html">tin foil</a>?</h4> </noscript> <!-- [note: highly prefer copper to aluminum or tin] --> # Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE Wei-Kai Lin, Ethan Mook, Daniel Wichs* Northeastern University and NTT Research December 8, 2022 ## Abstract A _(single server) private information retrieval (PIR)_ allows a client to read data from a public database held on a remote server, without revealing to the server which locations she is reading. In a _doubly efficient PIR (DEPIR)_, the database is first preprocessed, but the server can subsequently answer any client’s query in time that is sub-linear in the database size. Prior work gave a plausible candidate for a _public-key_ variant of DEPIR, where a trusted party is needed to securely preprocess the database and generate a corresponding public key for the clients; security relied on a new non-standard code-based assumption and a heuristic use of ideal obfuscation. In this work we construct the stronger _unkeyed_ notion of DEPIR, where the preprocessing is a deterministic procedure that the server can execute on its own. Moreover, we prove security under just the standard _ring learning-with-errors (RingLWE)_ assumption. For a database of size N and any constant ε > 0, the preprocessing run-time and size is O(N^(1+ε)), while the run-time and communication-complexity of each PIR query is poly log(N). We also show how to update the preprocessed database in time O(N^ε). Our approach is to first construct a standard PIR where the server’s computation consists of evaluating a multivariate polynomial; we then convert it to a DEPIR by preprocessing the polynomial to allow for fast evaluation, using the techniques of Kedlaya and Umans (STOC ’08). Building on top of our DEPIR, we construct general fully _homomorphic encryption for randomaccess machines (RAM-FHE)_, which allows a server to homomorphically evaluate an arbitrary RAM program P over a client’s encrypted input x and the server’s preprocessed plaintext input y to derive an encryption of the output P(x, y) in time that scales with the RAM runtime of the computation rather than its circuit size. Prior work only gave a heuristic candidate construction of a restricted notion of RAM-FHE. In this work, we construct RAM-FHE under the RingLWE assumption with circular security. For a RAM program P with worst-case runtime T, the homomorphic evaluation runs in time T^(1+ε) · poly log(|x| + |y|). *Research supported by NSF grant CNS-1750795, CNS-2055510 and the Alfred P. Sloan Research Fellowship. https://github.com/zhaowenlan1779/akita-inu # Project Akita Inu This is a toy implementation of the paper [Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE](https://eprint.iacr.org/2022/1703.pdf). This implementation almost exactly follows the paper, and is not intended, nor expected, to be practically useful. Licensed under MIT. ## Building Please add the `--recursive` flag when cloning this repo, or execute `git submodule update --init --recursive` afterwards. The build system is CMake. Requires a C++20-capable compiler, like a recent version of GCC or MSVC.