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 have already examined that 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 D_{R_q, \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 D_{R_q, \sigma}$. Then we put ciphertext $c = (c_0 = -a, c_1 = as+te+m = as+2e+m)$.
- Decryption. The decryption algorithm simply puts $m = c_0 + c_1s \mod t$, which means in our case \(c_0s + c_1 \mod 2 \equiv -as + as+2e+m \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. 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 D_{R_q, \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 D_{R_q, \sigma}$ and $e_2 \gets D_{R_q, \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 = -a’, c_1 = b’+m)$.
- 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
\(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).\)
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.