The GSW Encryption Scheme

We now describe the encryption scheme our compiler targets. GSW, introduced by Gentry, Sahai, and Waters in 2013, is one of the simplest fully homomorphic encryption schemes. It encrypts a single bit by hiding it inside a matrix, in such a way that a party with the secret key can extract it but an adversary without it cannot. Addition of ciphertexts is just matrix addition, and multiplication is matrix multiplication preceded by a bit-decomposition step that we describe below.

Ciphertexts as approximate eigenvectors

Fix $n, q \in \mathbb{Z}^{\ge 2}$, and let $\ell = \lceil \log_2(q)\rceil$ and $m = n\ell$. A ciphertext encrypting a message $\mu \in {0,1}$ is a matrix $C \in \mathbb{Z}_q^{n \times m}$ satisfying

$$\mathbf{s}^\top C ;=; \mu \cdot \mathbf{s}^\top G ;+; \mathbf{e}, \qquad (\star)$$

where:

• $\mathbf{s} \in \mathbb{Z}_q^n$ is the secret key,
• $\mathbf{e} \in \mathbb{Z}_q^m$ is a small noise vector, and
• $G \in \mathbb{Z}_q^{n \times m}$ is the gadget matrix, the fixed public matrix $G = I_n \otimes g^\top$ with $g^\top = \begin{bmatrix} 1 & 2 & 4 & 8 & \dots & 2^{\ell-1} \end{bmatrix}$.

GSW Homomorphic Operations

Addition. Given ciphertexts $C_1, C_2$ encrypting $\mu_1, \mu_2$ respectively, their sum $C_{\text{add}} = C_1 + C_2$ encrypts $\mu_1 + \mu_2$. To see why, we simply add the two instances of $(\star)$:

$$\mathbf{s}^\top C_{\text{add}} = \mathbf{s}^\top (C_1 + C_2) = (\mu_1 + \mu_2),\mathbf{s}^\top G + (\mathbf{e}_1 + \mathbf{e}_2).$$

The result is a valid ciphertext with noise $\mathbf{e}_1 + \mathbf{e}_2$, which remains small as long as the input noises are small.

Multiplication. Multiplication is more delicate. A naive attempt like $C_1 \cdot C_2$ would not preserve the invariant, and would also cause the noise to blow up. Instead, GSW uses the gadget matrix's inverse, $G^{-1}$, which maps each column of its input to its binary decomposition. Concretely, $G^{-1}: \mathbb{Z}_q^{n \times m} \to {0,1}^{m \times m}$ satisfies $G \cdot G^{-1}(A) = A$ for any matrix $A$, and note that its output has small entries (only 0s and 1s).

The homomorphic product is defined as $C_{\text{mult}} = C_1 \cdot G^{-1}(C_2)$. To verify correctness:

$$\mathbf{s}^\top C_{\text{mult}} = \mathbf{s}^\top C_1 \cdot G^{-1}(C_2) = (\mu_1,\mathbf{s}^\top G + \mathbf{e}_1),G^{-1}(C_2) = \mu_1,\mathbf{s}^\top C_2 + \mathbf{e}_1,G^{-1}(C_2).$$

Expanding $\mathbf{s}^\top C_2$:

$$= \mu_1(\mu_2,\mathbf{s}^\top G + \mathbf{e}_2) + \mathbf{e}_1,G^{-1}(C_2) = \mu_1 \mu_2,\mathbf{s}^\top G + \underbrace{\mu_1,\mathbf{e}_2 + \mathbf{e}1,G^{-1}(C_2)}{\text{new noise}}.$$

Because $G^{-1}(C_2)$ has entries in ${0,1}$, the term $\mathbf{e}_1,G^{-1}(C_2)$ stays controlled: the noise grows, but only by a small amount.

The corresponding Lean definitions are as follows, where bitDecompMatrix is $G^{-1}$:

def homAdd (c1 c2 : Ciphertext p) : Ciphertext p :=
  ⟨c1.mat + c2.mat⟩

def homMult (c1 c2 : Ciphertext p) : Ciphertext p :=
  ⟨c1.mat * bitDecompMatrix p.l p.q c2.mat p.hl⟩

The noise growth problem

Note that bit decomposition does not eliminate noise growth. Each homomorphic multiplication increases the noise, and after enough operations the noise can exceed $q/4$, at which point decryption fails. This limits the depth of circuits that can be evaluated: a fresh ciphertext can support only a bounded number of multiplications before becoming undecryptable.

A scheme that can evaluate circuits up to some fixed depth is called somewhat/leveled homomorphic (SWHE). To achieve fully homomorphic encryption, one can use bootstrapping, which homomorphically evaluates the decryption circuit to refresh a ciphertext's noise.

From Boolean circuits to GSW circuits

Since messages are single bits, one might expect homomorphic addition to give XOR and multiplication to give AND. Multiplication does give AND, since the product of two bits is always a bit. But homomorphic addition operates in $\mathbb{Z}_q$, not $\mathbb{Z}_2$: adding two encryptions of $1$ yields an encryption of $2$, not $0$. So homAdd alone does not give us XOR.

Instead, we build the universal gate NAND: $\text{NAND}(\mu_1, \mu_2) = 1 - \mu_1 \cdot \mu_2$. For binary inputs this always lands in ${0,1}$, since $\mu_1 \cdot \mu_2 \in {0,1}$. Because NAND is functionally complete, any Boolean circuit can be evaluated homomorphically using only this gate, and our compiler targets NAND as its only operation.

def homNAND (c1 c2 : Ciphertext p) : Ciphertext p :=
  let prod := homMult p c1 c2
  ⟨gadgetMatrix p.n p.l p.q - prod.mat⟩

Note that homNAND computes $G - C_1 \cdot G^{-1}(C_2)$, where $G$ serves as a noiseless encryption of $1$.

Noise growth in NAND gates. Since NAND combines an addition and a multiplication, we can ask how much noise it introduces. Suppose both input ciphertexts have noise bounded by $B$ in the infinity norm, and that the messages $\mu_1, \mu_2 \in {0,1}$ are binary. The NAND noise is the multiplication noise $\mu_1 \cdot \mathbf{e}_2 + \mathbf{e}_1,G^{-1}(C_2)$ (negated, but negation preserves the norm). The addition with the constant $1$ contributes no noise, since $1$ can be encrypted noiselessly as the gadget matrix $G$. By the triangle inequality, the NAND noise is bounded by:

$$|\mu_1 \cdot \mathbf{e}2|\infty + |\mathbf{e}1,G^{-1}(C_2)|\infty ;\leq; B + m \cdot B ;=; (m+1) \cdot B,$$

where the first term uses the fact that $\mu_1 \in {0,1}$, and the second uses the fact that $G^{-1}(C_2)$ has binary entries. Each NAND gate therefore multiplies the noise by a factor of at most $(m+1)$. For a circuit of depth $d$, the noise after evaluation is at most $(m+1)^d \cdot B_0$, where $B_0$ is the initial noise. Decryption remains correct as long as this quantity stays below $q/4$, which the scheme's parameters must be chosen to satisfy.