II. Post-quantum Cryptography: B-4. GLWE Cryptosystem
Published: Updated:
This post is based on The Beginner’s Textbook for Fully Homomorphic Encryption by Ronny Ko.
In this post, I provide a summary and review of “II. Post-quantum Cryptography: B-4. GLWE Cryptosystem.”
B-4. GLWE Cryptosystem
The GLWE cryptosystem is a generalized form to encompass both the LWE and RLWE cryptosystems.
1. Key Notations
Like in LWE and RLWE, a new public key $A$ is created for each ciphertext,
whereas the same secret key $S$ is used for all ciphertexts.
The GLWE ciphertext is defined as a tuple $({A_i}_{i=0}^{k-1}, B)$, where
\[B = \sum_{i=0}^{k-1}(A_i \cdot S_i) + \Delta \cdot M + E\]| Symbol | Meaning |
|---|---|
| $A_i \in R_{n,q}^k$, for $i = 0, \ldots, k-1$ | Public polynomials (freshly sampled per ciphertext) |
| $S_i \in R_{n,2}^k$, for $i = 0, \ldots, k-1$ | Secret polynomials (fixed) |
| $M \in R_{n,t}$, where $t < q$ and $t \mid q$ | Message polynomial |
| $E \leftarrow \chi_\sigma$ | Noise polynomial sampled from Gaussian distribution |
2. Relation to LWE and RLWE
GLWE generalizes both LWE and RLWE through its parameters $n$ and $k$:
| Cryptosystem | Parameter Setting | Secret Key |
|---|---|---|
| LWE | $n = 1$ (degree-0 polynomials = scalars) | $k$ scalar constants forming a vector |
| RLWE | $k = 1$ (single polynomial) | One $(n-1)$-degree polynomial $S_0$ |
| GLWE | General $n, k$ | $k$ polynomials of degree $(n-1)$ |
👉 LWE and RLWE are special cases of GLWE — GLWE unifies them under a single framework.
B-4.1 Setup
To be continued …
