Digital Log

    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.