PIR - Homework Solutions

GMW for Arithmetic Circuits

In this problem, we extend the GMW protocol to arithmetic circuits over the ring \(\mathbb{Z}_{2^\ell}\). In particular, each wire \(w\) carries a value \(v^w \in \mathbb{Z}_{2^\ell}\); the arithmetic circuit consists of ADD and MULT gates for addition and multiplication modulo \(2^{\ell}\).

Throughout the protocol, we keep the invariant that for each wire \(w\), the \(n\) parties hold additive secret shares for its value \(v^w\) over the ring \(\mathbb{Z}_{2^\ell}\), namely, each party hold a random share \(v^w_i \in \mathbb{Z}_{2^\ell}\) such that \(\sum_{i\in[n]} v^w_i = v^w \mod 2^\ell\).

  1. Inputs: For each input wire \(w\), say it carries an input from party \(P_k\) with input value \(v^w \in \mathbb{Z}_{2^\ell}\), how does \(P_k\) generate additive secret shares of \(v^w\) and distribute them among all the parties?

Party \(P_k\) randomly samples \(v^w_i \gets \mathbb{Z}_{2^\ell}\) for all \(i\in[n-1]\) and computes \(v^w_n := v^w -\sum_{i\in[n-1]}v^w_i \mod 2^\ell\). Then \(P_k\) sends \(v^w_i\) to party \(P_i\) for all \(i\in[n]\).

  1. ADD gates: For each addition gate, the \(n\) parties hold additive secret shares \(\{a_i\}_{i\in[n]}\) and \(\{b_i\}_{i\in[n]}\) for the two input wires with values \(a\) and \(b\), respectively. How can they generate additive secret shares \(\{c_i\}_{i\in[n]}\) for the output wire with value \(c=a+b \mod 2^\ell\)?

Each party \(P_i\) locally computes \(c_i:= a_i + b_i \mod 2^\ell\).

  1. MULT gates: For each multiplication gate, the \(n\) parties hold additive secret shares \(\{a_i\}_{i\in[n]}\) and \(\{b_i\}_{i\in[n]}\) for the two input wires with values \(a\) and \(b\), respectively. Now they want to generate additive secret shares \(\{c_i\}_{i\in[n]}\) for the output wire with value \(c=a\cdot b \mod 2^\ell\). Explain how this problem can be reduced to a Reshare protocol (between two parties over \(\mathbb{Z}_{2^\ell}\)). In the Reshare protocol, two parties hold inputs \(x,y\in \mathbb{Z}_{2^\ell}\) respectively; from the protocol they learn random \(r,s \in \mathbb{Z}_{2^\ell}\) respectively such that \(r+s = x \cdot y \mod 2^\ell\).

Note that \(c = (\sum_{i\in[n]} a_i)\cdot (\sum_{i\in[n]} b_i) = \sum_{i\in[n]} a_i \cdot b_i + \sum_{i,j\in[n], i \neq j} a_i \cdot b_j \mod 2^\ell\). Each party \(P_i\) can locally compute \(a_i \cdot b_i \mod 2^\ell\); then between every pair of parties \(P_i\) and \(P_j\) where \(i,j\in[n], i \neq j\), we only need a Reshare protocol for them to get random shares of \(a_i \cdot b_j\).

  1. Reshare: Design such a Reshare protocol between two parties over \(\mathbb{Z}_{2^\ell}\) using 1-out-of-2 OT. (Hint: Consider the bit decomposition of \(y\).)

In the Reshare protocol, two parties Alice and Bob hold inputs \(x,y\in \mathbb{Z}_{2^\ell}\) respectively; from the protocol they learn random \(r,s \in \mathbb{Z}_{2^\ell}\) respectively such that \(r+s = x \cdot y \mod 2^\ell\).

The two parties run \(\ell\) instances of 1-out-of-2 OT where Alice is the sender and Bob is the receiver. Consider the bit decomposition \(y\) as \(y = \sum_{t\in\{0,1,\dots,\ell-1\} }2^t \cdot b_t\).

For each \(t\in\{0,1,\dots,\ell-1\}\), Alice samples a random \(r_t \gets \mathbb{Z}_{2^\ell}\) and prepares two messages \(m_t^0 = - r_t \mod 2^\ell\) and \(m_t^1 = x \cdot 2^t - r_t \mod 2^\ell\) as the two OT messages for the \(t\)-th instance of OT; Bob prepares \(b_t\in\{0,1\}\) as the choice bit for the \(t\)-th instance of OT. From the \(t\)-th instance of OT, Bob learns \(s_t = x \cdot 2^t \cdot b_t - r_t \mod 2^\ell\).

Finally, Alice outputs \(r = \sum_{t\in\{0,1,\dots,\ell-1\} } r_t \mod 2^\ell\) and Bob outputs \(s = \sum_{t\in\{0,1,\dots,\ell-1\} } s_t \mod 2^\ell\). This is a random reshare since \(r+s= \sum_{t\in\{0,1,\dots,\ell-1\} } r_t +\sum_{t\in\{0,1,\dots,\ell-1\} } (x \cdot 2^t \cdot b_t - r_t) = x\cdot (\sum_{t\in\{0,1,\dots,\ell-1\} } 2^t \cdot b_t) = x \cdot y\) where \(r\) is randomly sampled.

Fully Homomorphic Encryption (FHE)

  1. In one sentence, what is fully homomorphic encryption? Give a potential application of FHE in practice. (Try to come up with one that was not covered in class!)

A homomorphic encryption scheme is an encryption scheme that allows one to compute a function on encrypted data directly, which results in an encryption of the output of the computation. If the encryption scheme supports such homomorphic evaluation for all polynomial sized circuits, then it is fully homomorphic.

  1. Intuitively speaking, what's the main reason that all somewhat homomorphic encryption (SWHE) schemes only support a bounded number of homomorphic operations, especially homomorphic multiplications?

In all the SWHE schemes, there is a small noise term in each ciphertext, which grows with homomorphic addition and multiplication operations. Once the noise becomes too large, it will affect the correctness of ciphertext decryption. The noise typically grows linearly in homomorphic additions and exponentially in homomorphic multiplications. Thus all the schemes only support a bounded number of homomorphic operations, especially homomorphic multiplications.

Private Information Retrieval (PIR)

  1. What are the similarities and differences between PIR and 1-out-of-\(n\) OT? Explain why 1-out-of-\(n\) OT is no better than sending the entire database to the client for solving the PIR problem.

Similarity: In both PIR and 1-out-of-\(n\) OT, the client (receiver) wants to retrieve one out of \(n\) messages from the server (sender) without revealing to the server (sender) which message was retrieved.

Difference: In 1-out-of-\(n\) OT, we want to ensure sender privacy where the receiver learns nothing beyond the retrieved message, while in PIR we don't require server privacy.

1-out-of-\(n\) OT also requires \(O(n)\) communication complexity, so it is no better than sending the entire database to the client for solving PIR.

  1. Let's look at the tradeoffs in choosing different values for \(d\), the dimension of the hypercube that we lay our data out as. What value should we choose to minimize the number of homomorphic multiplications (optimizing computation)? What value should we choose to minimize the size of the selection vector (optimizing communication)?

To minimize the number of homomorphic multiplications, we should choose \(d=1\). To minimize the size of the selection vector, we should choose \(d=\log n\).