Learning with Errors Public Key Cryptosystem with Its Security

Zhiyong Zheng, Kun Tian, Yi Zhang, Yunfan Lu

Engineering Research Center of Ministry of Education for Financial Computing and Digital Engineering, Renmin University of China, Beijing, China.

DOI: 10.4236/jis.2023.141003                

Abstract

The main purpose of this paper is to introduce the LWE public key cryptosystem with its security. In the first section, we introduce the LWE public key cryptosystem by Regev with its applications and some previous research results. Then we prove the security of LWE public key cryptosystem by Regev in detail. For not only independent identical Gaussian disturbances but also any general independent identical disturbances, we give a more accurate estimation probability of decryption error of general LWE cryptosystem. This guarantees high security and widespread applications of the LWE public key cryptosystem.

Keywords

Learning With Errors Problem, Cryptosystem, Decryption Error, Probability, Security

1. Introduction

In 2005, O. Regev proposed the first LWE public key cryptosystem in Tel Aviv University in Israel based on LWE distribution $A_{s,\chi }$. Because of this paper, Regev won the highest award for theoretical computer science in 2018—the Godel Award. The size of public key is $\tilde{O}\left(n^2\right)$ bits, and the size of private key s and ciphertext is $\tilde{O}\left(n\right)$ bits. The plaintext encrypted each time is 1 bit. In fact, the LWE public key cryptosystem is a probabilistic cryptosystem, which depends on a high probability algorithm. Since the security of LWE problem has been clearly proved, the LWE cryptosystem has received extensive attention as soon as it was proposed, and it becomes the most cutting-edge research topic in the lattice-based cryptosystem study.

Let p be a prime number, $m,n$ be two positive integers. Given a list of equations with error as follows:

$\{\begin{array}{l}\langle s,a_1\rangle {\approx }_{\chi }{v}_1\left(\text{mod}p\right)\text{,}\\ \langle s,a_2\rangle {\approx }_{\chi }{v}_2\left(\text{mod}p\right)\text{,}\\ ⋮\\ \langle s,a_m\rangle {\approx }_{\chi }{v}_m\left(\text{mod}p\right)\text{,}\end{array}$

where $v_i\in {\mathbb{Z}}_p$, $s\in {\mathbb{Z}}_p^n$, $a_i\in {\mathbb{Z}}_p^n$ are selected independently and uniformly, and $\langle s,a_i\rangle$ means the inner product of the vectors s and $a_i$. The errors $e_i\in {\mathbb{Z}}_p$ in the above equations come from a probability distribution $\chi :{\mathbb{Z}}_p\to {ℝ}^{+}$, i.e. for any $1\le i\le m$, we have $v_i=\langle s,a_i\rangle +e_i$ and $e_i\in {\mathbb{Z}}_p$ is generated independently according to the probability distribution $\chi$. The problem of finding $s\in {\mathbb{Z}}_p^n$ is denoted as ${\text{LWE}}_{p,\chi }$ [1] [2]. The LWE public key cryptosystem of Regev introduced in the next section is proposed based on this problem.

The LWE problem could be regarded as an extension of a well known problem in learning theory which is believed hard to solve. Many researchers worked on the LWE problem and proved that the complexity of the best known algorithm is running in exponential time of n [3] [4] [5] [6]. An important theorem that gives the difficulty of solving the LWE problem is at least as hard as that of hard problems on lattice, such as the determination of the shortest vector problem (GapSVP) and the continuous shortest vector problem (SIVP) [3], which is proved by a quantum polynomial probabilistic reduction algorithm. Since the academic community believes that the hard problems on lattice such as the SVP, SIVP and GapSVP problems can resist quantum computing effectively, that is, there are no known quantum algorithms to solve the hard problems on lattice, so that the security of the LWE public key cryptosystem is guaranteed. We will give a detailed proof for the security of the LWE cryptosystem proposed by Regev in 2005 in section 3. However, this cryptosystem could only encrypt a single bit of plaintext and the efficiency is low. In order to encrypt multiple bits of plaintext and improve the efficiency signally, Regev presented a general LWE cryptosystem in 2009. We gave a more precise estimation probability of decryption error based on independent identical Gaussian disturbances and any general independent identical disturbances in [7], which shows that the general LWE public key cryptosystem could have high security.

An application of the LWE cryptosystem is the fully homomorphic encryption (FHE) [8]. The earliest FHE cryptosystem was based on average-case assumptions about ideal lattices [9] [10]. Later, Brakerski and Vaikuntanathan constructed the second FHE cryptosystem, which was based on the LWE problem [11] [12]. In 2013, the third fully homomorphic encryption algorithm based on the LWE problem was proposed by Gentry, Sahai, and Waters, which is proved that has some unique and advantageous properties [13]. It also remains some improvable techniques which need to be studied in depth [14]. The main purpose of this paper is to introduce the LWE public key cryptosystem with the proof of its security mathematically, which guarantees the widespread applications of it.

2. LWE Cryptosystem of Regev

Let $n\ge 1$, $q\ge 2$ be positive integers, $\chi$ be a given probability distribution in ${\mathbb{Z}}_q$. The LWE distribution $A_{s,\chi }$ is

$\{\begin{array}{l}{A}_{s,\chi }=\left(a,b\right)\in {\mathbb{Z}}_q^n\times {\mathbb{Z}}_q,\\ b{\equiv }_{\chi }\langle a,s\rangle +e\left(\text{mod}q\right)\text{,}\end{array}$ (1.1)

where $a\in {\mathbb{Z}}_q^n$ is uniformly distributed, $s\in {\mathbb{Z}}_q^n$ is the private key chosen at random, $e\in {\mathbb{Z}}_q$, $e\leftarrow \chi$ is called error distribution. LWE cryptosystem depends on LWE distribution $A_{s,\chi }$, and its workflow has the following three steps:

1) Public key

First we choose $s\in {\mathbb{Z}}_q^n$ at random as the private key, let $m=O\left(n\log q\right)$. Then we choose m samples distributed from $A_{s,\chi }$, $\left(a_i,b_i\right)\in {\mathbb{Z}}_q^n\times {\mathbb{Z}}_q$, $e_i\in {\mathbb{Z}}_q$, $e_i\leftarrow \chi$, $1\le i\le m$. Let

$\bar{A}={\left[a_1,a_2,\cdots ,a_m\right]}_{n\times m}\in {\mathbb{Z}}_q^{n\times m},$

$b=\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right),e=\left(\begin{array}{c}{e}_1\\ e_2\\ ⋮\\ e_m\end{array}\right),e\leftarrow {\chi }^m,$

where $\bar{A}$ is a matrix uniformly at random, $e\leftarrow {\chi }^m$ indicates the m samples are independent. The public key of LWE cryptosystem is the following $\left(n+1\right)\times m$ matrix

$A=\left(\begin{array}{c}\bar{A}\\ b^{\prime }\end{array}\right)\in {\mathbb{Z}}_q^{\left(n+1\right)\times m}.$ (1.2)

If the uniformly random matrix $\bar{A}$ is given and saved for all the users of LWE cryptosystem, then the true public key is $b=\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right)\in {\mathbb{Z}}_q^m$ with size $O\left(m\right)=\tilde{O}\left(n\right)$. The public key and private key satisfy the following equation:

$\left(-s^{\prime },1\right)A{\equiv }_{\chi }{e}^{\prime }\left(\mathrm{mod}q\right)\text{.}$ (1.3)

2) Encryption.

In order to encrypt plaintext of 1 bit $u\in {\mathbb{Z}}_2$, let $x\in {\left\{0,1\right\}}^m$ be an uniformly distributed m dimensional vector with each entry 0 or 1. The ciphertext $c\in {\mathbb{Z}}_q^{n+1}$ is an $\left(n+1\right)$ dimensional vector in ${\mathbb{Z}}_q$, defined by

$f_A\left(u\right)=c=Ax+\left(\begin{array}{c}0\\ u\cdot \lfloor \frac{q}{2}\rfloor \end{array}\right)\in {\mathbb{Z}}_q^{n+1},$ (1.4)

where $0=\left(\begin{array}{c}0\\ 0\\ ⋮\\ 0\end{array}\right)\in {\mathbb{Z}}_q^n$, $u\lfloor \frac{q}{2}\rfloor \in {\mathbb{Z}}_q$, $\lfloor \frac{q}{2}\rfloor$ is the nearest integer to $\frac{q}{2}$. We call $f_A$ the encryption algorithm of LWE. In order to understand the encryption algorithm better, we give another definition of $f_A$.

The following set $\left\{1,2,\cdots ,m\right\}$ has $2^m$ subsets. We choose a subset $S\subset \left\{1,2,\cdots ,m\right\}$ uniformly at random which is called the index set. Then the encryption algorithm $f_A\left(u\right)$ for plaintext $u\in {\mathbb{Z}}_2$ is

$c=f_A\left(u\right)=\left(\begin{array}{c}{\displaystyle \underset{i\in S}{\sum }{a}_i}\\ {\displaystyle \underset{i\in S}{\sum }{b}_i}+u\lfloor \frac{q}{2}\rfloor \end{array}\right)\in {\mathbb{Z}}_q^{n+1}.$ (1.5)

In fact, the subset S is corresponding to the uniformly chosen vector $x\in {\left\{0,1\right\}}^m$. The above formula (1.5) was proposed by Regev originally.

3) Decryption

We use the private key $s\in {\mathbb{Z}}_q^n$ for decryption of the ciphertext c. Actually, we only need to decrypt for the last entry of vector c. We have

$f_A^{-1}\left(c\right)=\left(-s^{\prime },1\right)c=\left(-s^{\prime },1\right)Ax+u\lfloor \frac{q}{2}\rfloor {\equiv }_{\chi }{e}^{\prime }x+u\lfloor \frac{q}{2}\rfloor \left(\mathrm{mod}q\right)\text{.}$ (1.6)

The error samples are much smaller than q, namely

${\displaystyle \underset{i\in S}{\sum }{e}_i}=e^{\prime }x<\lfloor \frac{q}{2}\rfloor /2.$ (1.7)

Therefore, by comparing the distances between the right side of (1.6) and 0 or $\lfloor \frac{q}{2}\rfloor$, one can decrypt successfully:

$f_A^{-1}\left(c\right)=\{\begin{array}{l}0,\text{if}\left(-s^{\prime },1\right)c\text{iscloserto0,}\\ 1,\text{if}\left(-s^{\prime },1\right)c\text{iscloserto}\lfloor \frac{q}{2}\rfloor ,\end{array}$ (1.8)

finally we have $f_A^{-1}\left(c\right)=u$ and finish the whole workflow of LWE cryptosystem.

Both of the encryption algorithm and decryption algorithm of LWE are probabilistic algorithms, so we should verify the correctness, namely

$\mathrm{Pr}\left\{f_A^{-1}\left(c\right)=u\right\}\ge 1-\delta \left(n\right).$ (1.9)

Here $\delta \left(n\right)$ is a negligible function of n, i.e. $\delta \left(n\right)=o\left(\frac{1}{{\log }^{\epsilon }n}\right)$, $\forall \epsilon >0$, more precisely:

$\underset{n\to \infty }{\lim }\delta \left(n\right){\log }^{\epsilon }n=0,\forall \epsilon >0.$

We prove (1.9) with given discrete Gauss distribution $\chi ={\bar{\psi }}_{\alpha }$. For $a\in {\mathbb{Z}}_q$, ${\mathbb{Z}}_q=\left\{0,1,\cdots ,q-1\right\}$,

$\left|a\right|=\{\begin{array}{l}a,\text{if}0<a\le \lfloor \frac{q}{2}\rfloor ,\\ q-a,\text{if}\lfloor \frac{q}{2}\rfloor <a\le q-1.\end{array}$ (1.10)

For $x\in T=\left[0,1\right)$, we define

$\left|x\right|=\{\begin{array}{l}x,\text{if0}\le x<\frac{1}{2},\\ 1-x,\text{if}\frac{1}{2}\le x<1.\end{array}$ (1.11)

Lemma 1.1: Let $\delta >0$, $0\le k\le m$, if the distribution ${\chi }^k$ satisfies

$\underset{e~{\chi }^k}{\mathrm{Pr}}\left\{\left|e\right|<\lfloor \frac{q}{2}\rfloor /2\right\}>1-\delta ,$ (1.12)

then (1.9) holds, i.e.

$\mathrm{Pr}\left\{f_A^{-1}\left(c\right)=u\right\}>1-\delta .$

Proof: When we choose the error samples $e_i\in {\mathbb{Z}}_q$, $e_i\leftarrow \chi$, we can always guarantee $e_i=\left|e_i\right|$ without changing the probability distribution. By (1.7), suppose that $\left|S\right|=k$, the corresponding sample

$e=\left(\begin{array}{c}{e}_1\\ e_2\\ ⋮\\ e_k\end{array}\right),\left|e\right|={\displaystyle \underset{i=1}{\overset{k}{\sum }}\left|e_i\right|}={\displaystyle \underset{i=1}{\overset{k}{\sum }}{e}_i}.$

As long as (1.7) holds, i.e.

$\left|e\right|<\lfloor \frac{q}{2}\rfloor /2\Rightarrow f_A^{-1}\left(c\right)=u,$

then

$\mathrm{Pr}\left\{f_A^{-1}\left(c\right)=u\right\}\ge \mathrm{Pr}\left\{\left|e\right|<\lfloor \frac{q}{2}\rfloor /2\right\}>1-\delta .$

$\square$

Next we prove (1.12) holds for discrete Gauss distribution ${\bar{\psi }}_{\alpha }$ in ${\mathbb{Z}}_q$. The following assumptions are made for the selection of parameters:

$\{\begin{array}{l}n\ge 1,q\ge 2,n^2\le q\le 2n^2,\\ m=\left(1+\epsilon \right)\left(n+1\right)\log q,\epsilon >0\text{isanypositiverealnumber,}\\ \chi ={\bar{\psi }}_{\alpha \left(n\right)},\alpha \left(n\right)=o\left(\frac{1}{\sqrt{n}\log n}\right),\end{array}$ (1.13)

where the symbol o indicates

$\underset{n\to 0}{\lim }\alpha \left(n\right)\cdot \sqrt{n}\log n=0.$

For example, we can choose $\alpha \left(n\right)=\frac{1}{\sqrt{n}{\log }^{2}n}$, or

$\alpha \left(n\right)={\left(\sqrt{n}{\log }^{1+\epsilon }n\right)}^{-1},\forall \epsilon >0.$

Lemma 1.2: Under the condition for parameters of (1.13), for any $0\le k\le m$, we have

$\underset{e~{\bar{\psi }}_{\alpha \left(n\right)}^k}{\mathrm{Pr}}\left\{\left|e\right|<\lfloor \frac{q}{2}\rfloor /2\right\}>1-\delta \left(n\right),$ (1.14)

where $\delta \left(n\right)=o\left(\frac{1}{{\log }^{\epsilon }n}\right)$, $\forall \epsilon >0$, is a negligible function.

Proof: Based on (1.13), when $n\ge n_0$, it is easy to see that

$0\le k\le m\le 4\left(1+\epsilon \right)\left(n+1\right)\log n<\frac{n^2}{32}\le \frac{q}{32}.$

The k samples $e=\left(\begin{array}{c}{e}_1\\ ⋮\\ e_k\end{array}\right)$ distributed as ${\bar{\psi }}_{\alpha }^k$ could be obtained from the k samples $x_1,x_2,\cdots ,x_k$ of distribution ${\psi }_{\alpha }$, where

$x_i\in \left[0,\frac{1}{2}\right),e_i=\lfloor q{x}_i\rfloor \text{mod}q,1\le i\le k.$

Here the set of representative elements of ${\mathbb{Z}}_q$ is

${\mathbb{Z}}_q=\left\{a\in \mathbb{Z}|-\frac{q}{2}\le a<\frac{q}{2}\right\}.$

So we have

$\left|e\right|={\displaystyle \underset{i=1}{\overset{k}{\sum }}\left|e_i\right|}={\displaystyle \underset{i=1}{\overset{k}{\sum }}\lfloor q{x}_i\rfloor }\text{mod}q.$

Note that

${\displaystyle \underset{i=1}{\overset{k}{\sum }}\left(\lfloor q{x}_i\rfloor -q{x}_i\right)}\text{mod}q\le k\le \frac{q}{32},$

therefore,

${\displaystyle \underset{i=1}{\overset{k}{\sum }}q{x}_i\text{mod}q}\le \frac{q}{16}\Rightarrow \left({\displaystyle \underset{i=1}{\overset{k}{\sum }}{x}_i}\right)\text{mod}1\le \frac{1}{16},$

we have $\left|e\right|<\lfloor \frac{q}{2}\rfloor /2$. Since ${\displaystyle \underset{i=1}{\overset{k}{\sum }}{x}_i}$ mod 1 distributed as ${\psi }_{\sqrt{k}\alpha }$, where $\sqrt{k}\cdot \alpha =o\left(\frac{1}{\sqrt{\log n}}\right)$, so

$\mathrm{Pr}\left\{{\displaystyle \underset{i=1}{\overset{k}{\sum }}{x}_i\text{mod}1}<\frac{1}{16}\right\}=1-\delta \left(n\right),$

where $\delta \left(n\right)=\sqrt{k}\cdot \alpha =o\left(\frac{1}{\sqrt{\log n}}\right)$. We complete the proof.

$\square$

3. The Proof of Security

To prove the security of Regev’s cryptosystem, we first prove some general properties for the probability distribution of Abel group by Impagliazzo and Zurkerman [15].

Let G be a finite Abel group, $k\ge 1$ be a positive integer. For any $l$ elements $g_1,g_2,\cdots ,g_l\in G$, suppose $x\in {\left\{0,1\right\}}^l$, $g=\left(g_1,g_2,\cdots ,g_l\right)$, then

$gx={\displaystyle \underset{i=1}{\overset{l}{\sum }}{x}_i{g}_i},x_i=0\text{or}1$

is called a subsum of $\left\{g_1,g_2,\cdots ,g_l\right\}$. Randomly choose $x\in {\left\{0,1\right\}}^l$, let $gx$ denote the distribution of subsum, and let $U\left(G\right)$ denote the uniformly distribution on G.

Lemma 2.1: For any $l$ elements $\left\{g_1,g_2,\cdots ,g_l\right\}$ uniformly at random, the expectation of statistical distance between the distribution of subsum and the uniformly distribution on $U\left(G\right)$ is

$E\left(\Delta \left(gx,U\left(G\right)\right)\right)\le {\left(\left|G\right|/2^l\right)}^{\frac{1}{2}}.$

Specially, the probability that the statistical distance is larger than ${\left(\left|G\right|/2^l\right)}^{\frac{1}{4}}$ is no more than ${\left(\left|G\right|/2^l\right)}^{\frac{1}{4}}$, i.e.

$\begin{array}{l}\mathrm{Pr}\left\{\Delta \left(gx,U\left(G\right)\right)\ge {\left(\left|G\right|/2^l\right)}^{\frac{1}{4}}\right\}\\ \le {\left(\left|G\right|/2^l\right)}^{\frac{1}{4}}.\end{array}$

Proof: Let $g=\left(g_1,g_2,\cdots ,g_l\right)$ be $l$ group elements chosen at random, $h\in G$ is a given group element. Define $P_g(\; h\; )$

$\begin{array}{l}{P}_g\left(h\right)\\ =\frac{1}{2^l}\left|\left\{x\in {\left\{0,1\right\}}^l,gx={\displaystyle \underset{i=1}{\overset{l}{\sum }}{x}_i{g}_i=h}\right\}\right|,\end{array}$

we call $P_g\left(h\right)$ the distribution of subsum for g. In order to prove $P_g\left(h\right)$ is close to uniformly distribution, we first prove the $l_2$ norm between $P_g\left(h\right)$ and the uniformly distribution is very small. In fact, we have:

$\begin{array}{c}{\displaystyle \underset{h\in G}{\sum }{P}_g{\left(h\right)}^2}=\underset{x,x^{\prime }}{\mathrm{Pr}}\left\{gx=g{x}^{\prime }\right\}\\ =\frac{1}{2^l}+\underset{x,x^{\prime }}{\mathrm{Pr}}\left\{gx=g{x}^{\prime },x\ne x^{\prime }\right\}.\end{array}$

Note that for any $x\ne x^{\prime }$,

$\underset{g}{\mathrm{Pr}}\left\{gx=g{x}^{\prime }\right\}=\frac{1}{\left|G\right|}.$

So the expectation of $l_2$ norm for g satisfy

$\underset{g}{E}\left[{\displaystyle \underset{h\in G}{\sum }{P}_g{\left(h\right)}^2}\right]\le \frac{1}{2^l}+\frac{1}{\left|G\right|}.$

Finally, we have the following estimation

$\begin{array}{c}\underset{g}{E}\left[{\displaystyle \underset{h\in G}{\sum }\left|P_g\left(h\right)-\frac{1}{\left|G\right|}\right|}\right]\le \underset{g}{E}\left[{\left|G\right|}^{\frac{1}{2}}{\left({\displaystyle \underset{h\in G}{\sum }{\left(P_g\left(h\right)-\frac{1}{\left|G\right|}\right)}^2}\right)}^{\frac{1}{2}}\right]\\ ={\left|G\right|}^{\frac{1}{2}}\underset{g}{E}\left[{\left({\displaystyle \underset{h\in G}{\sum }{P}_g{\left(h\right)}^2-\frac{1}{\left|G\right|}}\right)}^{\frac{1}{2}}\right]\\ ={\left|G\right|}^{\frac{1}{2}}{\left[\underset{g}{E}\left({\displaystyle \underset{h\in G}{\sum }{P}_g{\left(h\right)}^2}\right)-\frac{1}{\left|G\right|}\right]}^{\frac{1}{2}}\\ \le {\left(\left|G\right|/2^l\right)}^{\frac{1}{2}}.\end{array}$

We complete the proof.

$\square$

The security of LWE public key cryptosystem by Regev is ascribed to the following theorem, which is the most important result in this section.

Theorem 1: For any $\epsilon >0$, $m\ge \left(1+\epsilon \right)\left(n+1\right)\log q$, if there is a probabilistic polynomial time algorithm W which distinguishes the plaintext $u=0$ or $u=1$ from the ciphertext c, then there exists a polynomial time algorithm solving the ${\text{D-LWE}}_{n,q,\chi ,m}$ problem.

Proof: The public key of LWE cryptosystem is $A=\left(\begin{array}{c}\bar{A}\\ b^{\prime }\end{array}\right)$, where $\bar{A}\in {\mathbb{Z}}_q^{n\times m}$ is a matrix uniformly at random, $b=\left(\begin{array}{c}{b}_1\\ ⋮\\ b_m\end{array}\right)\in {\mathbb{Z}}_q^m$ is an m dimensional vector chosen uniformly. The encryption function $f_A\left(u\right)$ is

$c=f_A\left(u\right)=Ax+\left(\begin{array}{c}0\\ u\lfloor \frac{q}{2}\rfloor \end{array}\right)\in {\mathbb{Z}}_q^{n+1},x\in {\left\{0,1\right\}}^m.$

Since W is a probabilistic polynomial time algorithm, suppose $P_0\left(W\right)$ is the probability that decrypting $u=0$ from $f_A\left(0\right)$ by W, and $P_1\left(W\right)$ is the probability that decrypting $u=1$ from $f_A\left(1\right)$, i.e.

$\{\begin{array}{l}{P}_0\left(W\right)=\mathrm{Pr}\left\{W\left(f_A\left(0\right)\right)=0\right\}.\\ P_1\left(W\right)=\mathrm{Pr}\left\{W\left(f_A\left(1\right)\right)=1\right\}.\end{array}$ (2.1)

If $b\in {\mathbb{Z}}_q^m$ is uniformly at random, then LWE distribution $A_{s,\chi }$ is uniformly LWE distribution. Let $P_u\left(W\right)$ be the probability of decryption successfully by W under the condition of uniformly distribution $A_{s,\chi }$. Suppose that

$\left|P_0\left(W\right)-P_1\left(W\right)\right|\ge \frac{1}{n^{\delta }},\delta >0.$ (2.2)

Under the assumption of (2.2), we will construct a new algorithm $W^{\prime }$ satisfying

$\left|P_0\left(W^{\prime }\right)-P_u\left(W^{\prime }\right)\right|\ge \frac{1}{2n^{\delta }}.$ (2.3)

By (2.2), we have

$\left|P_0\left(W\right)-P_u\left(W\right)\right|\ge \frac{1}{2n^{\delta }},\text{or}\left|P_1\left(W\right)-P_u\left(W\right)\right|\ge \frac{1}{2n^{\delta }}.$

If the first inequality of the above formula holds, let $W^{\prime }=W$. If the second inequality of the above formula holds, then construct $W^{\prime }$ as follows. Let the function $\sigma$ be $f_A\left(u\right)\to f_A\left(u\right)+\left(\begin{array}{c}0\\ \frac{q-1}{2}\end{array}\right)$. Thus, $\sigma$ maps the LWE distribution $\left(\bar{A},b\right)$ to $\left(\bar{A},b+\frac{q-1}{2}\right)$. If b is uniformly at random, so is $b+\frac{q-1}{2}$. We define $W^{\prime }$ to be the decryption on LWE distribution $\left(\bar{A},b+\frac{q-1}{2}\right)$ by W. According to (1.5),

$P_0\left(W\right)=P_1\left(W^{\prime }\right),P_1\left(W\right)=P_0\left(W^{\prime }\right),$

So $W^{\prime }$ is the algorithm which satisfies (2.3).

Let $s\in {\mathbb{Z}}_q^n$, the public key sample satisfies distribution of $\left(\bar{A},b\right)\in {\mathbb{Z}}_q^{n\times m}\times {\mathbb{Z}}_q^m=A_{s,\chi }$. Let $P_0\left(s\right)$ be the probability of decryption $u=0$ successfully by $W^{\prime }$, i.e.

$P_0\left(s\right)=\mathrm{Pr}\left\{W^{\prime }\left(f_A\left(0\right)\right)=0\right\}.$

Similarly, let $P_u\left(s\right)$ be the probability of decryption successfully by $W^{\prime }$ if $\left(\bar{A},b\right)$ is uniformly at random. Suppose

$\left|\underset{s}{E}\left[P_0\left(s\right)\right]-\underset{s}{E}\left[P_u\left(s\right)\right]\right|\ge \frac{1}{2n^{\delta }},$ (2.4)

We define

$Y=\left\{s\in {\mathbb{Z}}_q^n|\left|P_0\left(s\right)-P_u\left(s\right)\right|\ge \frac{1}{4n^{\delta }}\right\}.$ (2.5)

It’s easy to prove: if $s\in {\mathbb{Z}}_q^n$ is uniformly distributed, then we have

$\left|Y\right|/q^n\ge \frac{1}{4n^{\delta }}.$

Therefore, in order to prove theorem 1, we need to find an algorithm Z to determine whether the LWE distribution $A_{s,\chi }$ is uniformly at random for any $s\in Y$. The construction of algorithm Z: let R be a probability distribution on ${\mathbb{Z}}_q^n$ which is uniform LWE distribution or general LWE distribution when $s\in Y$, i.e.

$R=\text{uniformLWEdistribution,or}R=A_{s,\chi },s\in Y.$

Let $\bar{A}=\left[a_1,\cdots ,a_m\right]\in {\mathbb{Z}}_q^{n\times m}$, $b=\left(\begin{array}{c}{b}_1\\ ⋮\\ b_m\end{array}\right)\in {\mathbb{Z}}_q^m$ be m random samples from distribution R. Let $P_0\left(R\right)$ be the probability of decryption $u=0$ successfully by $W^{\prime }$, where $\left(a,b\right)=A_{s,\chi }$, $s\in Y$. In the same way, suppose $P_u\left(R\right)$ is the probability of decryption $u=0$ successfully by $W^{\prime }$ if R is uniform LWE distribution. We estimate $P_0\left(R\right)$ and $P_u\left(R\right)$ by using the algorithm $W^{\prime }$ polynomial times so that the error could be controlled within $\frac{1}{64n^{\delta }}$. If $\left|P_0\left(R\right)-P_u\left(R\right)\right|\ge \frac{1}{16n^{\delta }}$, then the algorithm Z is effective, otherwise it is noneffective.

We first confirm: if R is uniform LWE distribution, then Z is noneffective with high probability. Because in this case, $\left(\bar{A},b\right)\in {\mathbb{Z}}_q^{n\times m}\times {\mathbb{Z}}_q^m$, b is uniformly at random. According to lemma 2.1, the Abel group $G={\mathbb{Z}}_q^n\times {\mathbb{Z}}_q$, we have

$\left|P_0\left(R\right)-P_u\left(R\right)\right|\le 2^{-\Omega \left(n\right)},$

In this case, Z is noneffective.

If $R=A_{s,\chi }$, where $s\in Y$, we are to prove the algorithm Z is effective with probability $\frac{1}{\text{Poly}\left(n\right)}$, i.e. one can distinguish $s\in Y$ from uniform distribution. Since $\left|P_0\left(R\right)-P_u\left(R\right)\right|\ge \frac{1}{4n^{\delta }}$, in the average sense we get

$\mathrm{Pr}\left\{\left|P_0\left(R\right)-P_u\left(R\right)\right|\ge \frac{1}{8n^{\delta }}\right\}\ge \frac{1}{8n^{\delta }}.$

Thus, the algorithm Z is effective for $A_{s,\chi }$, $s\in Y$ with positive probability. We complete the proof of theorem 1.

$\square$

4. General LWE-Based Cryptosystem

We introduced the LWE cryptosystem proposed by Regev in section 2, and proved its security in section 3. However, it could only encrypt a single bit of plaintext and the efficiency is low. Based on the definition and properties of rounding function, Regev presented a general LWE cryptosystem in 2009, which could encrypt multiple bits of plaintext $v\in {\mathbb{Z}}_t^l$ with size $O\left(t^l\right)$ and improve the efficiency signally. In this section, we introduce general LWE cryptosystem first. Then we discuss the probability of decryption error for this cryptosystem and prove that it could be sufficiently small with suitable parameters. So we verify our core result that the LWE cryptosystem could have high security.

Definition 3.1: Let $t,q,l$ be positive integers, we define function $F:{\mathbb{Z}}_t^l\to {\mathbb{Z}}_q^l$ as

$F\left(a\right)=\left(\lfloor \frac{q}{t}{a}_1\rfloor ,\lfloor \frac{q}{t}{a}_2\rfloor ,\cdots ,\lfloor \frac{q}{t}{a}_l\rfloor \right)\in {\mathbb{Z}}_q^l,\forall a=\left(a_1,a_2,\cdots ,a_l\right)\in {\mathbb{Z}}_t^l,$ (3.1)

and the “inverse function” $F^{-1}:{\mathbb{Z}}_q^l\to {\mathbb{Z}}_t^l$ as

$F^{-1}\left(b\right)=\left(\lfloor \frac{t}{q}{b}_1\rfloor ,\lfloor \frac{t}{q}{b}_2\rfloor ,\cdots ,\lfloor \frac{t}{q}{b}_l\rfloor \right)\in {\mathbb{Z}}_t^l,\forall b=\left(b_1,b_2,\cdots ,b_l\right)\in {\mathbb{Z}}_q^l.$ (3.2)

Let $t,q,m,n,l,r$ be positive integers, $q>t$, function F and its “inverse function” are defined in 3.1. The workflow of general LWE cryptosystem is as follows:

1) Selection of private key S: $S\in {\mathbb{Z}}_q^{n\times l}$ is an $n\times l$ matrix uniformly at random in ${\mathbb{Z}}_q$.

In the LWE cryptosystem introduced in section 2, the private key is an n dimensional randomly chosen vector $s\in {\mathbb{Z}}_q^n$. To encrypt more general plaintext $v\in {\mathbb{Z}}_t^l$, we randomly select $l$ private keys $s_1,s_2,\cdots ,s_l\in {\mathbb{Z}}_q^n$ independently and form an $n\times l$ matrix $S=\left[s_1,s_2,\cdots ,s_l\right]$. This is the private key S for general LWE cryptosystem.

2) Public key.

When the private key $S\in {\mathbb{Z}}_q^{n\times l}$ is fixed, in order to choose samples from LWE distribution, we first select m uniform n dimensional vectors $a_1,a_2,\cdots ,a_m\in {\mathbb{Z}}_q^n$ in ${\mathbb{Z}}_q^n$ and form a uniform random matrix

$A={\left[a_1,a_2,\cdots ,a_m\right]}_{n\times m}\in {\mathbb{Z}}_q^{n\times m}.$

Then we generate $m\times l$ noise matrix samples $E={\left(E_{ij}\right)}_{m\times l}$ from distribution ${\bar{\psi }}_{\alpha }$, i.e. $E_{ij}\in {\mathbb{Z}}_q$, $E_{ij}\leftarrow {\bar{\psi }}_{\alpha }$, $1\le i\le m$, $1\le j\le l$, and the $m\times l$ samples are mutually independent. Finally we get an $m\times l$ matrix P

$P=A^{\text{T}}S+E={\left(\begin{array}{ccc}\langle a_1,s_1\rangle +E_{11}& \cdots & \langle a_1,s_l\rangle +E_{1l}\\ ⋮& \ddots & ⋮\\ \langle a_m,s_1\rangle +E_{m1}& \cdots & \langle a_m,s_l\rangle +E_{ml}\end{array}\right)}_{m\times l}.$

The public key of LWE cryptosystem is $\left(A,P\right)$, which is similar to that in section 2. Here we only change the public key from $b\in {\mathbb{Z}}_q^m$ to $m\times l$ matrix $P\in {\mathbb{Z}}_q^{m\times l}$. If the uniformly random matrix A is given and saved for all the users of LWE cryptosystem, then the true public key is the matrix P, and the public key and private key satisfy the following equation

$P-A^{\text{T}}S{\equiv }_{{\bar{\psi }}_{\alpha }}E\left(\mathrm{mod}q\right)\text{.}$

3) Encryption.

To encrypt multiple bits of plaintext $v\in {\mathbb{Z}}_t^l$, let $a\in {\left\{-r,-r+1,\cdots ,r\right\}}^m$ be an m dimensional vector with each entry selected uniformly in $\left\{-r,-r+1,\cdots ,r\right\}$,

i.e. a is uniformly distributed. Ciphertext $\left(\begin{array}{c}u\\ c\end{array}\right)$ is an $n+l$ dimensional vector, defined by

$g_{A,P}\left(v\right)=\left(\begin{array}{c}u\\ c\end{array}\right),u=Aa,c=P^{\text{T}}a+F\left(v\right),$

where F is defined in (3.1), and $g_{A,P}$ is called the encryption algorithm of LWE cryptosystem.

4) Decryption.

Given ciphertext $\left(u,c\right)$ and the private key S, we compute $F^{-1}\left(c-S^{\text{T}}u\right)$ as the result of decryption. We have

$\begin{array}{c}{F}^{-1}\left(c-S^{\text{T}}u\right)=F^{-1}\left(P^{\text{T}}a+F\left(v\right)-S^{\text{T}}u\right)\\ =F^{-1}\left({\left(A^{\text{T}}S+E\right)}^{\text{T}}a+F\left(v\right)-S^{\text{T}}Aa\right)\\ =F^{-1}\left(E^{\text{T}}a+F\left(v\right)\right).\end{array}$

We need to calculate the probability of decryption error for this cryptosystem, namely, the probability of $F^{-1}\left(E^{\text{T}}a+F\left(v\right)\right)\ne v$. The following theorem 2 gives a more precise upper bound estimation than [2] for this probability, which is proved in [7].

Theorem 2: Suppose $q>t$, we have the following inequality of the probability of decryption error

$\mathrm{Pr}\left\{F^{-1}\left(E^{\text{T}}a+F\left(v\right)\right)\ne v\right\}\le 2l\left(1-\Phi \left(\frac{q-t}{2\alpha tq}\sqrt{\frac{6\pi }{mr\left(r+1\right)}}\right)\right).$ (3.3)

Here $\Phi$ is the cumulative distribution function of the standard normal distribution, i.e. $\Phi \left(x\right)={\displaystyle {\int }_{-\infty }^x\frac{1}{\sqrt{2\pi }}{\text{e}}^{-\frac{t^2}{2}}\text{d}t}$.

The upper bound could be as closed as 0 if we choose $\alpha$ small enough. It means that the probability of decryption error for the LWE cryptosystem could be made very small with an appropriate setting of parameters.

We could also estimate the probability of decryption error for the LWE cryptosystem when the noise matrix $E={\left(E_{ij}\right)}_{m\times l}$ is chosen independently from a general common variable, rather than Gauss distribution. By central limit theorem [16], general disturbances could be approximated as Gaussian disturbances. We have the following theorem 3 which is proved in [7].

Theorem 3: $q>t$, $E={\left(E_{ij}\right)}_{m\times l}$, each element $E_{ij}$ is selected independently from a common random variable of mean 0 and standard deviation $\beta$. For any $\delta >0$, we can find positive integer m, such that the following inequality of the probability of decryption error holds,

$\mathrm{Pr}\left\{F^{-1}\left(E^{\text{T}}a+F\left(v\right)\right)\ne v\right\}\le 2l\left(1-\Phi \left(\frac{q-t}{2\beta t}\sqrt{\frac{3}{mr\left(r+1\right)}}\right)\right)+l\delta .$ (3.4)

Here $\Phi$ is the cumulative distribution function of the standard normal distribution, i.e. $\Phi \left(x\right)={\displaystyle {\int }_{-\infty }^x\frac{1}{\sqrt{2\pi }}{\text{e}}^{-\frac{t^2}{2}}\text{d}t}$.

This probability could also be closed to 0 if we choose the parameter $\beta \sqrt{m}$ and $\delta$ small enough. Therefore the probability of decryption error of the LWE cryptosystem for general disturbance could be made very small, which leads to high security.

5. Conclusion

In this work, we introduce the LWE cryptosystem of Regev, and give a detailed proof for the security of LWE public key cryptosystem by Regev. We also introduce general LWE cryptosystem presented by Regev in order to encrypt multiple bits of plaintext and improve the efficiency signally. For not only independent identical Gaussian disturbances but also any general independent identical disturbances, we give a more accurate estimation probability of decryption error of general LWE cryptosystem. The upper bound probability could be closed to 0 if we choose applicable parameters, which means that the probability of decryption error for general LWE cryptosystem could be sufficiently small. So we verify that the LWE public key cryptosystem could have high security.

Acknowledgements

The authors would like to thank the editors and reviewers for their constructive comments, which help improve the study significantly.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Regev, O. (2005) On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, 22-24 May 2005, 84-93. https://doi.org/10.1145/1060590.1060603
[2]	Micciancio, D. and Regev, O. (2009) Lattice-Based Cryptography. In: Bernstein, D.J., Buchmann, J. and Dahmen, E., Eds., Post-Quantum Cryptography, Springer, Berlin, 147-191. https://doi.org/10.1007/978-3-540-88702-7_5
[3]	Regev, O. (2009) On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Journal of the ACM, 56, Article No. 34. https://doi.org/10.1145/1568318.1568324
[4]	Ajtai, M., Kumar, R. and Sivakumar, D. (2001) A Sieve Algorithm for the Shortest Lattice Vector Problem. Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Heraklion, 6-8 July 2001, 601-610. https://doi.org/10.1145/380752.380857
[5]	Blum, A., Kalai, A. and Wasserman, H. (2003) Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model. Journal of the ACM, 50, 506-519. https://doi.org/10.1145/792538.792543
[6]	Kumar, R. and Sivakumar, D. (2001) On Polynomial Approximation to the Shortest Lattice Vector Length. Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington DC, 7-9 January 2001, 126-127.
[7]	Zheng, Z. and Tian, K. (2022) On the LWE Cryptosystem with More General Disturbance. Journal of Information Security, 13, 127-139. https://doi.org/10.4236/jis.2022.133008
[8]	Rivest, R., Adleman, L. and Dertouzos, M. (1978) On Data Banks and Privacy Homomorphism. In: DeMillo, R.A., Ed., Foundations of Secure Computation, Academic Press, New York, 169-180.
[9]	Gentry, C. (2009) Fully Homomorphic Encryption Using Ideal Lattices. Proceedings of the 41st Annual ACM Symposium on Theory of Computing, Bethesda, 31 May-2 June 2009, 169-178. https://doi.org/10.1145/1536414.1536440
[10]	Dijk, M., Gentry, C., Halevi, S. and Vaikuntanathan, V. (2010) Fully Homomorphic Encryption over the Integers. International Conference on Theory and Applications of Cryptographic Techniques, French Riviera, 30 May-3 June 2010, 24-43. https://doi.org/10.1007/978-3-642-13190-5_2
[11]	Brakerski, Z. and Vaikuntanathan, V. (2011) Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. Annual Cryptology Conference, Santa Barbara, 14-18 August 2011, 505-524. https://doi.org/10.1007/978-3-642-22792-9_29
[12]	Brakerski, Z. and Vaikuntanathan, V. (2011) Efficient Fully Homomorphic Encryption from (Standard) LWE. IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, 22-25 October 2011, 831-871. https://doi.org/10.1109/FOCS.2011.12
[13]	Gentry, C., Sahai, A. and Waters, B. (2013) Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. Annual Cryptology Conference, Santa Barbara, 18-22 August 2013, 75-92. https://doi.org/10.1007/978-3-642-40041-4_5
[14]	Islam, M., Islam, M., Islam, N. and Shabnam, B. (2018) A Modified and Secured RSA Public Key Cryptosystem Based on “n” Prime Numbers. Journal of Computer and Communications, 6, 78-90. https://doi.org/10.4236/jcc.2018.63006
[15]	Impagliazzo, R. and Zuckerman, D. (1989) How to Recycle Random Bits. Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Research Triangle Park, 30 October-1 November 1989, 248-253. https://doi.org/10.1109/SFCS.1989.63486
[16]	Riauba, B. (1975) A Central Limit Theorem for Dependent Random Variables. Lithuanian Mathematical Journal, 15, 185-200. https://doi.org/10.1007/BF00975432