# Symmetric Private Information Retrieval (SPIR) built on Spiral

*Ian Goldberg (iang@uwaterloo.ca), July 2022*

This code implements Symmetric Private Information Retrieval, building
on the Spiral PIR library (this code is not written by the Spiral
authors).

Spiral is a recent single-server (computational) PIR system from 2022:

  * Samir Jordan Menon, David J. Wu,
"Spiral: Fast, High-Rate Single-Server PIR via FHE Composition".
IEEE Symposium on Security and Privacy, 2022.
eprint:
[https://eprint.iacr.org/2022/368](https://eprint.iacr.org/2022/368),
code:
[https://github.com/menonsamir/spiral-rs](https://github.com/menonsamir/spiral-rs)

In ordinary PIR, the client learns the database record they were looking for, and the server does not learn which record that was.  The client is _not_ prevented, however, from learning _additional_ database records.  Downloading the whole database, for example, can be seen as a trivial form of PIR (though one that transfers way too much data, except for tiny databases).

In Symmetric PIR (SPIR), the client must learn only one database record, in addition to the server learning no information about which record that was.  SPIR is similar to oblivious transfer (OT), except that SPIR aims to have sublinear communication (at no time is something the size of the whole database downloaded), while OT does not have that restriction.

This code builds SPIR from ordinary PIR (using Spiral), using a strategy based on that of Naor and Pinkas:

  * Moni Naor and Benny Pinkas, "Oblivious Transfer and Polynomial Evaluation".
STOC 1999.  paper: [https://dl.acm.org/doi/10.1145/301250.301312](https://dl.acm.org/doi/10.1145/301250.301312)

The general strategy is this (for a database with N=2^r records):

  1. Server: Encrypt each record of the database with a unique key
  2. Client: Use 1-of-N OT to retrieve exactly one key
  3. Client: Privately download the encrypted record and decrypt it with the key retrieved above

In the Naor and Pinkas paper, step 3 was just trivial download of the whole encrypted database, but we use Sprial to privately retrieve the encrypted record of interest.  Note, however, that the client will typically learn additional nearby records as well, which is why we need to encrypt each record separately.

The 1-of-N OT is built from r 1-of-2 OTs in the same manner as in the Naor and Pinkas paper: the server picks r pairs of random keys, and the client chooses one key from each pair, according to the bits of the desired query index value.  Then each database entry is encrypted with the combination of keys associated with its index.

The Naor and Pinkas paper uses this for its encryption, where F is a pseudorandom function (PRF) family:

   Enc[j] = Db[j] XOR F\_{K_1,j1}(j) XOR F\_{K_2,j2}(j) XOR ... XOR F\_{K_r,jr}(j)

where j1,j2,...,jr are the bits of j, as j ranges from 0 to N-1.

We instead use:

   Ktot = K_1,j1 XOR K_2,k2 XOR ... XOR K_r,kr

   Enc[j] = Db[j] XOR F\_{Ktot}(j)

That is, Naor and Pinkas XOR the _outputs_ of the PRF, whereas we XOR the _keys_.  This requires a slightly stronger assumption on the PRF family (for example, that the functions with different keys are independent, even if the keys have some known XOR relation), but we're going to use AES for F, so that should be fine.

For the 1-of-2 OT protocol, we base it on the simple one from the 1989 paper of Bellare and Micali:

  * Mihir Bellare and Silvio Micali, "Non-Interactive Oblivious Transfer and Applications".  CRYPTO 1989.  paper: [https://cseweb.ucsd.edu/~mihir/papers/niot.pdf](https://cseweb.ucsd.edu/~mihir/papers/niot.pdf)

We slightly optimize the protocol in that instead of the client sending both β0 and β1 to the server, and the server checking that their sum (in elliptic curve terms) is C, the client just sends β0 and the server computes β1 = C-β0.  In addition, the server sends back the two keys ElGamal-encrypted to the keys β0 and β1, where the client can know the private key for at most one of them.  Bellare and Micali's paper does this as (r0\*G, H(r0\*β0) XOR K0, r1\*G, H(r1\*β1) XOR K1), whereas we use the slightly more efficient (r\*G, H(r\*β0) XOR K0, H(r\*β1) XOR K1).

## Running the code

To run the code:

`cargo run --release 20`

Where `20` is the value of r (that is, the database will have N=2^20 entries).  Each entry is 8 bytes.  There are three phases of execution: a one-time Spiral public key generation (this only has to be done once, regardless of how many SPIR queries you do), a preprocessing phase per SPIR query (this can be done _before_ knowing the contents of the database on the server side, or the desired index on the client side), and the runtime phase per SPIR query (once those two things are known).

A sample output (for r=20):

```
===== ONE-TIME SETUP =====

Using a 2048 x 4096 byte database (8388608 bytes total)
OT one-time setup: 3064 µs
Spiral client one-time setup: 224935 µs, 10878976 bytes

===== PREPROCESSING =====

rand_idx = 425489 rand_pir_idx = 831
Spiral query: 691 µs, 32768 bytes
key OT query in 365 µs, 640 bytes
key OT serve in 1860 µs, 1280 bytes
key OT receive in 1148 µs

===== RUNTIME =====

Send to server 8 bytes
Server encrypt database 89036 µs
Server load database 974249 µs
expansion (took 166596 us).
Server compute response 344613 µs, 14336 bytes (*including* the above expansion time)
Client decode response 888 µs
index = 948810, Response = 9488100948830
```

The various lines show the amount of compute time taken and the amount of data transferred between the client and the server.  The last line shows the random index that was looked up, and the database value the client retrieved.  The value for index i should be (10000001*i+20).