We have already examined the Ring-LWE problem in a previous post, so now let’s consider some practical examples of what we can build using it. In my opinion, 1 is one of the most interesting and fundamental works. In this post, I briefly go through this paper, leaving some comments collected from different materials.
We know that the Ring-LWE problem can be defined as a search problem (where it is hard to find $s \in R$ for known $a,b \in R$ where $b = a \cdot s + e \in R$) and a decision problem (where it is hard to distinguish a pair $a,b$ from a random pair of polynomials). The hardness of these problems results in a pretty efficient scheme of homomorphic encryption.
Symmetric encryption
In general, the public parameters of the presented encryption scheme are as follows:
- $n$ a power of 2,
- $q$ a big prime,
- $t$ sufficiently smaller than $q$, prime,
- $\sigma$ a standard deviation, usually for a Gaussian distribution.
In lattice-based constructions, the Gaussian distribution is used in most cases due to its favorable properties, such as being preserved under mathematical operations. We later use $x \gets \mathcal{X}_\sigma$ to mean that the value $x$ is a random value from $R_q$ with standard deviation $\sigma$, regardless of the selected distribution.
Next, we define two rings $R_q = \mathbb{Z}_q[x]/(x^n+1)$ and $R_t = \mathbb{Z}_t[x]/(x^n+1)$. For real applications, it is convenient to use $t = 2$, which means that each value from $R_t=R_2$ is a binary string of length $n$.
- Key generation. We set the key to a random value $s \gets R_q$.
- Encryption. Using $t = 2$, for the message $m \in {0,1}^n = R_2$, we generate a random $a \gets R_q$ and $e \gets \mathcal{X}_\sigma$. Then, we set the ciphertext $c = (c_0 = as+te+m = as+2e+m, c_1 = -a)$.
- Decryption. The decryption algorithm simply sets $m = c_0 + c_1s \mod t$, which means, in our case, \(c_0 + c_1s \mod 2 \equiv as+2e+m-as \mod 2\equiv 2e+m \mod 2 \equiv m\).
The security of this scheme relies on the inability to distinguish a pair $(a,as+2e)$ from $(a,u)$, where $a,u \in R_q$ are random polynomials if the Ring-LWE problem is hard for the selected parameters. The presented scheme maintains IND-CPA security but is not IND-CCA secure, because we can freely modify any ciphertext while it will still be valid, and thus we can potentially extract some useful information from this “feature.” Basically, such a property is called malleability.
Public-key encryption
Following the same parameters as in the symmetric scheme, we additionally introduce a standard deviation $\sigma’$ which is sufficiently larger than $\sigma$.
- Key generation. We set the private key to a random value $s \gets R_q$. Then, we set the public key to a pair $(a, b=as+te=as+2e)$, where $a\gets R_q$ and $e \gets \mathcal{X}_\sigma$.
- Encryption. Using $t = 2$, for the message $m \in {0,1}^n = R_2$ and public key $(a, b) \in R_q^2$, we set $e_0,e_1\gets \mathcal{X}\sigma$ and $e_2 \gets \mathcal{X}{\sigma’}$. Then, we set $a’ = ae_0+te_1 = ae_0+2e_1$ and $b’ = be_0 + te_2 = be_0 + 2e_2$. Then, we set the ciphertext $c = (c_0 = b’+m, c_1 = -a’)$.
- Decryption. The decryption is the same as in the symmetric scheme: $m = c_0 + c_1s \mod t$.
Let’s investigate how the security of this scheme is achieved. Having
\[b' = be_0 + 2e_2 = ase_0+tee_0 + 2e_2,\]we modify it as follows
\[\begin{gathered} b' = ase_0+2ee_0 + 2e_2 = ase_0+2ee_0 + 2e_2 + 2e_1s - 2e_1s =\\ s(ae_0 + 2e_1) + 2(ee_0 + e_2 - e_1s) = a's + 2(ee_0 + e_2 - e_1s). \end{gathered}\]If the standard deviation of $e_2$ is sufficiently large, then
\[b' \approx a's + 2e_2,\]which means that the pair $(a’, b’)$ is indistinguishable from a pair of random polynomials if the Ring-LWE problem is hard for the selected parameters.
Homomorphic properties
Using Ring-LWE for ciphers is useful not only because of its resistance to quantum attacks, but also because it allows building homomorphic ciphers that support both addition and multiplication of ciphertexts (yeah, Fully Homomorphic Encryption). Unfortunately, because of some limitations, the number of such operations is limited; this is why such schemes are called Somewhat Homomorphic Encryption (SWHE).
First of all, let’s define the equivalence relation between ciphertexts. We saw in the example above that our ciphertext contains only two values, but it is not a strict restriction. For our homomorphic purposes we allow $(c_0, \dots, c_d), d \geq 1$ to be a valid ciphertext and say that $(c_0, \dots, c_d, 0) \equiv (c_0, \dots, c_d)$. It basically means that we can pad any ciphertext to any desired length.
Then, we define the addition of ciphertexts as follows:
\[\forall d \geq 1\colon (c_0, \dots, c_d) + (c_0', \dots, c_d') = (c_0 + c_0', \dots, c_d + c_d').\]The correctness of this formula can be easily verified. Note that we require the ciphertexts to be the same length (you can always pad the smaller one). The ability to decrypt these ciphertexts, if they were initially valid, depends on the growth of the error. So, depending on the error’s upper and lower bounds, we can allow some finite number of additions until the ciphertext becomes too noisy to decrypt (basically, in our example, if any coefficient of $2e$ becomes bigger than $q$, it may become an odd value, which will affect the message after taking the modulus). This rule also applies to multiplication, but unfortunately, it becomes noisy much faster.
\[\forall d,p \geq 1\colon\; (c_0, \dots, c_d) \cdot (c_0', \dots, c_p') = (\hat{c}_0, \dots, \hat{c}_{d+p}),\]where
\[\forall k \in \{0, 1, \dots d+p\}\colon\;\;\hat{c}_k = \sum_{i \in \{0, \dots d\}, j \in \{0, \dots p\}\colon i + j = k} c_i + c_j'.\]The decryption itself is easy:
\[m = c_0 + c_1s + c_2s^2 + \dots + c_d s^d \mod t.\]