Introduction

Retrieving information from databases pulls a constant activity on the daily routine, concurrently, its privacy concern when it comes to sensitive data develop a parallel problem. Private information retrieval (PIR) is a privacy protocol that allows a user to download a required message from a set of messages stored in a database without revealing the index of the required message to the databases.

In other words, PIR is protocol in which from one side, a possibly untrusted server holds a public database $DB$ with $N$ records. On the other side, a client wants to query for record $i \in {0 \cdots N-1}$, without letting the server learn the queried item they are looking up (and, hence, learning the value $v$ associated with $i$ they are interested in). A naive solution involves the client locally downloading the whole $DB$, but that can be expensive: the goal of PIR is to both preserve privacy and be more efficient than the total cost of downloading the whole $DB$. There are many proposed solutions for this problem, and for this Capstone Project, we will explore the ones that use Fully Homomorphic Encryption (FHE) as a cryptographic primitive.

Preliminaries and Fundamentals

Stateful Private Information Retrieval

It is important to note that the PIR interaction is divided into two parts: (1) offline query-independent and (2) online query-dependent.

• Offline Phase:

  • ssetup$(1^{\lambda})$: An algorithm that runs on the server, generating the initial parameter ip.
  • cinit(ip): An algorithm where the client initializes with the initial parameters ip. It generates a message msg that is sent to a server during the offline phase. This phase can be omitted, making the scheme client-independent for preprocessing.
  • spreproc(ip, DB, msg): Server preprocessing algorithm that runs using the initial parameters ip, the server’s database DB, and the client’s message msg. It generates a set of public parameters pp that are downloaded by the client.
  • cpreproc(ip, pp): Client preprocessing algorithm that runs on the server generated with the public parameters (ip, pp) and generates a state st.

• Online Phase:

  • query(st, i): Algorithm in which the client generates a query q for the item at index i in the server’s DB, and optionally returns an updated state st'.
  • respond(DB, q): Algorithm in which the server generates a response r to be sent to the client.
  • process(st, r): Algorithm in which the client uses this response r and generates an element x from the DB.

FrodoPIR Original Scheme

The protocol consists of 5 parts, where:

• Offline:
  1. In the offline phase, the server interprets the database as a matrix and applies a compression function to reduce its size, creating a global parameter. This compression function reduces the size of the DB by $m/\lambda$, where $\lambda$ is the security parameter and $m$ is the number of elements in the DB. Therefore, note that the parameter is not linear in the size of the DB.
  2. Also in the offline phase, the client downloads the public parameters and computes $c$ sets of preprocessed query parameters.
• Online:
  1. In the online phase, the client uses a set of preprocessed query parameters to create the encrypted query vector and sends it to the server.
  2. Still in the online phase, the server responds to this query by multiplying the query vector with the DB matrix.
  3. Finally, the client returns the result by decrypting the response using the preprocessed query parameters.

Objectives

The goal of the project approach is to reduce the computational cost of the online query processing, allowing the client to deal with multiple indices simultaneously. By structuring the database as a $\sqrt{m} \times \sqrt{m}$ matrix $D$, each cell representing a different element in $DB$, the client sends then two query vectors $v_{\text{row}}$ and $v_{\text{col}}$, each of size $\sqrt{m}$. The server then computes matrix-vector products to obtain the given entries.

You can download the document here!

>> Home