We have already examined the Ring-LWE problem in previous post so now let’s consider some practical examples of what we can build using it. In my opinion, 1 stands for one of the most interesting and fundamental work. 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 decision problem (where it is hard to distinguish pair $a,b$ from the random pair of polynomials). The hardness of these problems resulted in a pretty efficient scheme of homomorphic encryption.
Symmetric encryption
In general, the public parameters of the presented encryption scheme is 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 notate $x \gets \mathcal{X}_\sigma$ meaning value $x$ is a random value from $R_q$ with standard deviation $\sigma$ independent 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 put key a random value $s \gets R_q$.
- Encryption. Using $t = 2$, for the message $m \in {0,1}^n = R_2$ we generate random $a \gets R_q$ and $e \gets \mathcal{X}_\sigma$. Then we put ciphertext $c = (c_0 = as+te+m = as+2e+m, c_1 = -a)$.
- Decryption. The decryption algorithm simply puts $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 lies on the unavailability to distinguish a pair $(a,as+2e)$ from the $(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 still will be valid, and thus we can potentially extract some useful information from this “feature”. Basically, such property is called malleability.
Public-key encryption
Following the same parameters as in symmetric scheme, we additionally introduce a standard deviation $\sigma’$ which is sufficiently larger than $\sigma$.
- Key generation. We put private key a random value $s \gets R_q$. Then, we put public key 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 put $e_0,e_1\gets \mathcal{X_\sigma}$ and $e_2 \gets \mathcal{X}_{\sigma’}$. Then, we put $a’ = ae_0+te_1 = ae_0+2e_1$ and $b’ = be_0 + te_2 = be_0 + 2e_2$. Then we put ciphertext $c = (c_0 = b’+m, c_1 = -a’)$.
- Decryption. The decryption is the same as in symmetric scheme: $m = c_0 + c_1s \mod t$.
Let’s investigate how the security if 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 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 quantum attacks resistance, but also because it allows building a homomorphic ciphers which supports both addition and multiplication of ciphertexts (yeah, the 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$ 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 addition of ciphertext 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 ciphertext be the same length (you can always pad the smaller one). The availability 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 become 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 is also applied to the multiplication, but unfortunately it becomes noisy a lot 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.\]