FHE + threshold decryption proposal for private state sync

[kike]

Summary. This is a proposal for the private state sync problem. It leverages fully homomorphic encryption (FHE) and threshold decryption.

Roles. A set of n users (which is ever growing) that want to receive messages anonymously, an append-only bulletin board \mathsf{BB} where the messages are posted, and e.g. three third parties (servers) TP_1, TP_2, TP_3 that do the hard work. The servers are untrusted, but it is assumed that only a fraction of them collude.

Setup.

• The servers have secret-shared a decryption key of an FHE scheme with plaintext \mathbb{Z}_p. pk is public, sk_t is held by TP_t for t=1,2,3.
• Users have registered their identites with TP_t, and they can later prove/sign in with their identities.

The basic idea

A sender encrypts receiver identity j_i\in\{1,\ldots,n\} an attaches the ciphertext c_i to its message m_i.

When a recipient R with identity k pops in, TP_1,TP_2,TP_3 use m_i,c_i from \mathsf{BB} to derive a ciphertext \tilde{c}_i that encrypts m_i if j_i = k, else encrypts 0.

Then, each TP_t partially decrypts all \tilde{c}_i and sends the partial decryption vector \mathbf{d}_t to R, who can combine and retrieve. See diagram below (sorry, seems drawn by a kid…)

Details

Identify the set of n users with a subset \mathcal{U} = \{u_1,\ldots,u_n\}\subset\mathbb{Z}_p of the plaintext space.

Step 1. The sender publishes an encryption of u_{j_i}, where j_i is the recipient of the message. Thus \mathsf{BB} contains pairs (m_i,c_i=Enc_{pk}(u_{j_i}))

Step 2. On recipient’s request with identity k, each server TP_t downloads \mathsf{BB} and for each pair m_i,c_i homomorphically derives a ciphertext \tilde{c}_i encrypting m_i\cdot L_{k}(u_{j_i}). Here L_k(X) is the k-th lagrange polynomial over \mathcal{U}:

L_k(x) = \begin{cases} 1 & \text{if } x = u_k\\ 0 & \text{otherwise} \end{cases}

Note that L_k(X) is a polynomial of degree at most n-1 whose coefficients are known (k is known), so L_k(j_i) can be computed homomorphically.

Step 3. Each server TP_t, answers to recipient k with a vector of partial decryptions \mathbf{d}_t of the derived ciphertexts \tilde{\mathbf{c}}=(\tilde{c}_1,\ldots,\tilde{c}_N)

Step 4. Last, recipient k combine the shares. By construction it holds

\mathsf{combine}(d_{1,i},d_{2,i},d_{3,i}) = \begin{cases} m_i & \text{if } j_i = k\\ 0 & \text{otherwise} \end{cases}

Compact retrieval

As described so far, the proposal is of little use: for each item in \mathsf{BB} the recipient must combine the partial decryptions. A combinatorial argument can be used to reduce the size of the vector \mathbf{d}_t returned by TP_t.

This part is somewhat standard and we can borrow existing techniques from the literature.

Details

For example, the OMR scheme describes the following bucketing strategy. Let M be an upper bound on the number of messages received by each user.

Consider M buckets, then in step 3, and before partial decrypting, the servers:

1. randomly place each derived ciphertext \tilde{c}_i in a bucket
2. homomorphically add up all ciphertexts in the same bucket

This results in the recipient only combining N/M partial decryptions. The approach works assuming that the event of ‘having more than one ciphertext addressed to the same recipient in the same bucket’ happens with negligible probability.

Optimizations

Opt #1 Less computation by the servers: homomorphic multiply

In the basic idea, the server performs O(n) homomorphic computation, where n is the number of users. We can have an exponential improve --i.e. servers perform O(\log(n)) work-- by indexing user identity k with its binary encoding \mathbf{k}\in\{0,1\}^\ell of length \ell=\lceil\log(n)\rceil and leveraging homomorphic multiplication.

Details

The goal now is to compute the equality function E_{\mathbf{j}}(X_1,\ldots,X_\ell) over the boolean hypercube \{0,1\}^\ell:

E_\mathbf{k}(x_1,\ldots,x_\ell) = \begin{cases} 1 & \text{if } (x_1,\ldots,x_\ell) = \mathbf{k}\\ 0 & \text{otherwise} \end{cases}

Its multilinear extension to \mathbb{Z}_p^\ell is the multivariate polynomial:

\tilde{E}_\mathbf{k}(X_1,\ldots,X_\ell) := \prod_{r=1}^\ell(k_rX_r+(1-X_r)(1-k_r))

\tilde{E}_\mathbf{k} can be evaluated with 4\ell-1 additions and multiplications, i.e. with O(\log(n)) operations.

Aside note: The polynomial \tilde{E}_\mathbf{k} arises in the context of arithmetizing an R1CS instance as a sumcheck instance in the Spartan SNARK.

In step 1, the sender now attaches \ell ciphertexts \mathbf{c}_i = (c_{i,1},\ldots,c_{i,\ell}) to \mathsf{BB}. One per bit of the recipient identity \mathbf{j}_i. Thus, c_{i,r}:= Enc_{pk}(j_{i,r}) for r = 1,\ldots,\ell.

In step 2, to answer query from recipient \mathbf{k}, the servers derive homomorphically the ciphertext

\tilde{c}_i:=Enc_{pk}(m_i\cdot\tilde{E}_{\mathbf{k}}(\mathbf{j}_i)) = m_i \cdot \prod_{r=1}^\ell Enc_{pk}(j_{i,r}k_r+(1-k_r)(1-j_{i,r}))

Opt #2 Sender publishes just one ciphertext: batch-encrypt bits

By accounting for large set of n users we have increased communication bandwidth from sender to bulletin board by a \log(n) factor. It can be put it down to a single ciphertext again if all the bits of the user identity are batch-encrypted.

Details

Depending on what FHE scheme used, we can work with plaintext vectors of s slots each \mathbf{x}\in\mathbb{Z}_p^S. In step 1 the sender encrypts the recipient identity \mathbf{j}_{i} in a single ciphertext, one bit in each slot. The servers, starts step 2 by unpacking each c_i.

Assume \ell=S for simplicity. \mathsf{unpack} operation:

Enc_{pk}(j_{i,1},\ldots,j_{i,\ell})\stackrel{\mathsf{rotate}\text{ by } r}{\longrightarrow} Enc_{pk}(j_{i,r},\ldots,j_{i,\ell},j_{i,1},\ldots,j_{i,r-1}) \stackrel{\mathsf{mult}\text{ by }\mathbf{e}_1}{\rightarrow}Enc_{pk}(j_{i,r},0,\ldots,0)

Unpacking costs \ell rotations and \ell multiplications by \mathbf{e}_1.

Opt #3 Doing less server computation: SIMD operations

Now that the sender encrypts receiver’s bits \mathbf{j}_i in a single ciphertext, the server applies single-instruction multiple-data (SIMD) operations to homomorphically compute encryptions of \tilde{E}_{\mathbf{k}}(\mathbf{j}_i) on request for recipient \mathbf{k}.

Details

Specifically, for recipient \mathbf{k}, let c_i=Enc_{pk}(j_{i,1},\ldots,j_{i,\ell}) be the ciphertext computed by the sender. The servers compute the \ell factors f_r:=j_{i,r}k_r+(1-k_r)(1-j_{i,r}) for r\leq\ell using the following SIMD operation on the packed ciphertext c_i:

\mathsf{simd}(c_i,\mathbf{k}):=c_i\cdot\mathbf{k}+(\mathbf{1}-\mathbf{k})\cdot(\mathbf{1}-c_i).

Then, unpack each factor f_r from c'_i as explained above, and homomorphically multiply the results to obtain an encryption of \tilde{E}_\mathbf{k}(\mathbf{j}_i). Summarizing, the servers do step 2 as follows:

Enc_{pk}(j_{i,1},\ldots,j_{i,\ell})\stackrel{\mathsf{simd}}{\rightarrow} Enc_{pk}(f_{i,1},\ldots,f_{i,\ell})\stackrel{\mathsf{unpack}} {\longrightarrow} \begin{cases} Enc_{pk}(f_{i,1},0,\ldots,0)\\ \vdots\\ Enc_{pk}(f_{i,\ell},0,\ldots,0) \end{cases}

\stackrel{\mathsf{mult}}{\longrightarrow} = Enc_{pk}(\prod_{r=1}^\ell f_{i,r},0,\ldots,0) = Enc_{pk}(\tilde{E}_\mathbf{k}(\mathbf{j}_i))

\mathsf{simd}+\mathsf{unpack}+\mathsf{mult} requires \ell multiplications by plaintext \mathbf{e}_1, \ell-1+2 homomorphic multiplications, and 3 homomorphic additions/subtractions. Before we needed it 4\ell-1 homomorphic additions and 4\ell-1 homomorphic multiplications. But now we are doing \ell rotations, which are expensive.

Opt #4 Compacting servers response: pack evaluations

Servers pack S ciphertexts into a single one before compacting their response. The combinatorial strategy can now be done over N/S ciphertexts instead of N.

A further servers’ side improvement is to homomorphically multiply by \mathbf{m}:=(m_1,\ldots,m_S)\in\mathbb{F}_p^S after the packing operation (which saves homomorphic multiplications by a factor of S ).

Details

operation \mathsf{pack}.

\begin{cases} Enc_{pk}(\tilde{E}_{\mathbf{j}_1}(\mathbf{k}),0,\ldots,0)\\ Enc_{pk}(\tilde{E}_{\mathbf{j}_2}(\mathbf{k}),0,\ldots,0)\stackrel{\mathsf{rotate}\text{ by }1}{\longrightarrow} Enc_{pk}(0,\tilde{E}_{\mathbf{j}_2}(\mathbf{k}),0,\ldots,0)\\ \vdots\\ Enc_{pk}(\tilde{E}_{\mathbf{j}_S}(\mathbf{k}),0,\ldots,0)\stackrel{\mathsf{rotate}\text{ by } S-1}{\longrightarrow} Enc_{pk}(0,\ldots,0,\tilde{E}_{\mathbf{j}_S}(\mathbf{k})) \end{cases}

\stackrel{\mathsf{add}\text{ (}S-1\text{ times)}}{\longrightarrow} Enc_{pk}(\tilde{E}_{\mathbf{j}_1}(\mathbf{k}),\ldots,\tilde{E}_{\mathbf{j}_S}(\mathbf{k}))

Packing costs S-1 rotations and S-1 homomorphic additions.

Remarks and questions

Remarks

• There is no communication across the servers; they only homomorphically derive a ciphertext, each on their own.
• In principle an MPC protocol could be used instead. The drawback is that the sender needs to communicate to the servers the shares of the receiver’s identity. The advantage is that only the message is published in the bulletin board.
• We avoid recryption, which is the expensive part of the OMR scheme, by encrypting under a single public key and performing threshold decryption. Thus, we achieve better performance (purportedly) at the expense of a strong assumption.
• If messages do not fit in a plaintext slot \mathbb{Z}_p, can be split it into chunks and encrypt each separately.

Questions

• Main drawback is the assumption on threshold decryption. Does key switching help in getting rid of it in any way?
• What exact combinatorial strategy should be used?
• What FHE scheme? How many slots S?
• To avoid retrieving messages for other users, servers only partiall decrypt the right ciphertext \tilde{c}_i. Can honest servers be fooled to partially decrypt something else?