Fhe-Simons-Institute

Notes from this video intro.

Properties and Limitations

• Chosen-ciphertext security: HE is malleable by design, so this cannot be achieved

  • But weaker notions, like CCA1 can be achieved.

• Multi-hop: Can we apply Eval to previously evaluated ciphertexts?

  • Yes, but not always.

• Function privacy: Does $Eval_{pk}(F,\ldots)$ hide $f$?

  • Usually you can achieve this

• Obfuscation: FHE does not do this.

• RAM: FHE does not do random access.

  • RAM can compute some functions much faster.
  • In general random access isn't possible on encrypted data (not surprising).
  • Possible to do Oblivious RAM which is interactive between client/server.

• Multi-Key: FHE does not do multi-key automatically

  • Some schemes can achieve this however.

• Public Key Scheme:

  • Theorem: There's an easy black-box transformation from secret-key HE to public-key HE.

Construction

Two necessary pieces:

1. Express function $f$ as a circuit of addition and multiplication of bits.
2. Encryption that supports addition and multiplication of bits (hard part).

Note: this isn't a true ring homomorphism:

• Otherwise zero-encryption form a linear subspace; how would you hide this?

Noise

Technique: ciphertext has noise that hides the message.

Example: SWHE over integers

• Secret: large odd integer $n$
• Public key: $\{x_i = q_in + 2r_i\}$.
• You can add ciphertexts $c = c_1 + c_2 \mod n$
  • But noise grows with each add/multiply/polynomial operation.
  • Once noise grows past $n$, decryption fails.

We'll focus on Gentry-Sahai-Waters scheme, HE based on LWE.

Regev's Encryption Scheme

• $KeyGen(1^n)$:
  • Choose secret key $t = (1, \textbf{s})^t \in \mathbb{Z_q}^n$.
  • Public key: random $B \in \mathbb{Z_q}^{m\times n}$ but restricted to $B\textbf{t}$ "small" modulo $q$.
• $Encrypt(B, \mu \in \{0,1\})$:
  • Pick random $\textbf{r} \in \{0, 1\}^m$
  • Output $\textbf{c} \leftarrow (\mu, 0, \ldots, 0) \cdot \frac{2}{q} + \textbf{r}B$.
• $Decrypt(\textbf{c}, \textbf{t})$:
  • $\langle \textbf{c}, \textbf{t} \rangle = \mu \cdot \frac{q}{2} + \textbf{r} B \textbf{t} = \mu \cdot \frac{q}{2} + \text{``small"}$
  • Recover $\mu$ as the most significant bit of $\langle \textbf{c}, \textbf{t} \rangle$ modulo $q$.
• Properties:
  • If decision-LWE is hard, ciphertext are indistinguishable from uniform vectors over $\mathbb{Z_q}$.
  • Supports homomorphic addition.
  • What about multiplication of ciphertext vectors?
    • We could take the tensor product... but there are problems there.
    • Instead, turn the ciphertexts into matrices and use matrix multiplication.

Matrix version

• $KeyGen(1^n)$: same as above
  • Choose secret key $\textbf{t} = (1, \textbf{s})^t \in \mathbb{Z_q}^n$.
• $Encrypt(\mu \in \{0,1\})$:
  • Choose $C_0 \in \mathbb{Z_q}^{n\times m}$ such that each row is a Regev-encryption of $\textbf{0}$ and $C_0 \times \textbf{t}$ is small.
  • Output $C \leftarrow \mu \cdot I + C_0$.
• $Decrypt(C, \textbf{t})$:
  • Set $\textbf{z} = [C \times \textbf{t}]_q = \mu\cdot \textbf{t} + small$
  • Output 0 if $\textbf{z}$ is small, 1 if $\textbf{z}$ is close to $\textbf{t}$.
• Note: $t$ is an approximate eigenvector of $C$.
• Multiplication works but you get a large error term:
  • $\mu_2 \cdot \textbf{e}_1 + C_1 \times \textbf{e}_2$
  • where $C_1 \times \textbf{e}_2$ is a large term we'd like to get rid of.

Gadgets

To constraint the noise, we use a gadget matrix. It essentially takes a matrix of given dimension with large values, and transforms it into a higher dimensional matrix with smaller sized values.

$$G \in \mathbb{Z_q}^{m\times n} \quad\text{ with inverse transformation }\quad G^{-1}: \mathbb{Z_q}^{m\times n} \to \mathbb{Z_q}^{m\times m}$$

such that $\forall C \in \mathbb{Z_q}^{m \times n}:$

1. $G^{-1}(C) \in \mathbb{Z_q}^{m\times m}$ is small
2. $G^{-1}(C) \times G = C$

To use this, now the encryption of $\mu$ is a matrix $C \in \mathbb{Z_q}^{m \times n}$ such that

$$C \times \textbf{t} = \mu \cdot (G \times \textbf{t}) + e$$

So for $Enc$ we set $C = \mu \cdot G + C_0$ instead of $\mu \cdot I + C_0$.
The result: instead of a $C_1 \times \textbf{e}_2$ error term, we end up with $G^{-1}(C_1) \times \textbf{e}_2$, which is a much smaller term.

We end up with something somewhat homomorphic: supporting circuits with $\log_{m+1}(q)$ levels.