GSW encryption

The GSW encryption is a public-key encryption scheme based on the Learning With Errors (LWE) problem. ECLib implements the following algorithms.

Key generation

The key generation algorithm takes \((m, n, q, \sigma)\) as input and outputs public parameters \((m, n, q, \sigma, \ell, N)\), public key \(B\), and secret key \(s\), where \(m\), \(n\), and \(q\) are positive integers, \(\sigma\) is a positive real number, \(\ell = \lceil \log_2 q \rceil\), \(N = (n + 1) \ell\), \(s \in \mathbb{Z}_q^n\) is a random vector, \(B = [b^\top \ A^\top]^\top \in \mathbb{Z}^{(n + 1) \times m}\), \(A \in \mathbb{Z}_q^{n \times m}\) is a random matrix, \(b = s^\top A + e^\top \bmod q\), and \(e \in \mathbb{Z}^m\) is a random vector sampled from \(m\)-dimensional discrete Gaussian distribution with mean zero and variance \(\sigma\). The plaintext and ciphertext spaces are given by \(\mathcal{M} = \mathbb{Z}_q\) and \(\mathcal{C} = \mathbb{Z}_q^{(n + 1) \times N}\), respectively.

Encryption

The encryption algorithm takes the public parameters, public key, and a plaintext \(m \in \mathcal{M}\) as input and outputs

\[ B R + m G \bmod q, \]

where \(R \in \mathbb{Z}_2^{m \times N}\) is a random matrix, \(G = I_{n + 1} \otimes g\) is a gadget matrix, \(I_{n + 1}\) is the identify matrix of size \(n + 1\), \(g = [2^0 \ 2^1\ \cdots \ 2^{\ell - 1}]\), and \(\otimes\) denotes the Kronecker product.

Decryption

The decryption algorithm takes the public parameters, secret key, and a ciphertext \(c \in \mathcal{C}\) as input. Suppose that

\[\begin{split} c &= \begin{bmatrix} c_1 & \cdots & c_N \end{bmatrix}, \quad c_i \in \mathbb{Z}_q^{n + 1}, \\ \begin{bmatrix} x_0 \\ \vdots \\ x_{\ell - 1} \end{bmatrix} &= \begin{bmatrix} 1 & -s^\top \end{bmatrix} \begin{bmatrix} c_1 & \cdots & c_\ell \end{bmatrix} \bmod q. \end{split}\]

The algorithm outputs

\[ \sum_{i=0}^{\ell-1} 2^i b_i \bmod q, \]

where

\[\begin{split} b_0 &= \left\lfloor \frac{ x_{\ell - 1} }{ 2^{\ell - 1} } \right\rceil \bmod 2, \\ b_i &= \left\lfloor \frac{ x_{\ell - i - 1} - \sum_{j=1}^i 2^{\ell - i + j - 2} x_{j - 1} }{ 2^{\ell - 1} } \right\rceil \bmod 2, \quad i = 1, \dots, \ell - 1. \end{split}\]

Addition

The addition algorithm takes the public parameters and two ciphertexts \(c_1, c_2 \in \mathcal{C}\) as input and outputs

\[ c_1 + c_2 \bmod q. \]

Integer multiplication

The integer multiplication algorithm takes the public parameters, a plaintext \(m \in \mathcal{M}\), and a ciphertext \(c \in \mathcal{C}\) as input and outputs

\[ m c \bmod q. \]

Multiplication

The multiplication algorithm takes the public parameters and two ciphertexts \(c_1, c_2 \in \mathcal{C}\) as input and outputs

\[ c_1 \begin{bmatrix} G^{-1}(c_{2,1}) & \cdots & G^{-1}(c_{2,N}) \end{bmatrix} \bmod q, \]

where \(c_2 = [c_{2,1} \ \cdots \ c_{2,N}]\), and \(G^{-1}: \mathbb{Z}_q^{n + 1} \to \{0, 1\}^N\) is a bit decomposition function such that \(G G^{-1}(v) = v\) for all \(v \in \mathbb{Z}_q^{n + 1}\).