Quanta Magazine: Cryptographers Devise an Approach for Total Search Privacy

[Undescribed Horrific Abuse, One Victim & Survivor of Many]

> 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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 2022-1703.pdf
Type: application/pdf
Size: 745702 bytes
Desc: not available
URL: <https://lists.cpunks.org/pipermail/cypherpunks/attachments/20231107/e6ced715/attachment-0001.pdf>