# An Identity-Based Anti-Quantum Privacy-Preserving Blind Authentication in Wireless Sensor Networks
## 2 Preliminaries
### NTRU Lattice, Gaussians Sampling and Rejection Sampling on Lattice  
Let \(\alpha\) and \(\gamma\) be the vectors, \(p\) and \(N=2^{p}\) be integers, \(q\) be a prime which is greater than \(5\). Then we denote \(R=Z[x]/(x^{N}+1)\) as a ring. We denote \(f=\Sigma_{i=0}^{N-1}f_{i}x^{i}\) and \(g=\Sigma_{i=0}^{N-1}g_{i}x^{i}\) as polynomials in \(R\). \(R^{\times}\) is a set that all the elements have inverse in \(R\). We write \(<\alpha,\gamma>\) as vectors' inner product and \(||\alpha||\) as \(\alpha\)'s Euclidean norm. We write \(R_{q}=Z_{q}[x]/(x^{N}+1)\) as the ring. We denote polynomial multiplication and concatenation as \(f,g\text{ mod }(x^{N}+1)\) and \((f,g)\in R^{2N}=R^{1\times 2}\) in \(R\) respectively. Next, we introduce the definitions of NTRU lattice, Gaussians sampling [29], and Rejection sampling [14]. NTRU lattice is used for constructing NTRUEncrypt and NTRUSign. These cryptosystems have high-efficiency, extremely tight keys, and are sufficiently secure once properly parameterized. The NTRU lattice is introduced as follows:  
**Definition 1** (NTRU lattice). : _Let \(d,e\in\mathbf{R}\), \(h=e\times d^{-1}\text{ mod }q\). Then \(\boldsymbol{\mathcal{L}}_{h,q}=\{u,v\in R^{2}:u+v\times h=0\text{ mod }q\}\) is defined as NTRU Lattice. Meanwhile, \(\mathcal{L}_{h,q}\) is a \(\mathbf{R}^{2N}\) full-rank lattice \(\left( \begin{array}{cc}-C(h)&I\\ qI&O\end{array} \right)\), in which \(I\) is a unit matrix, \(O\) is a null matrix, \(C(h)\) is a matrix as follows: \(\left( \begin{array}{cccc}h_{0}&h_{1}...&h_{N-1}\\ -h_{N-1}&h_{0}&h_{N-2}\\.&.&.\\ -h_{1}&-h_{2}&h_{0}\end{array} \right)\)._  
The security of our IDBS is based on R-\(SIS\) problem over NTRU lattice, it is defined as follows:  
**Definition 2** (\(R\)-\(SIS_{q,1,2,\theta}^{x}\) on NTRU lattice). : _in a ring \(\mathbf{R}=Z[x]/(x^{N}+1)\), \(\kappa\) is denoted as a distribution, in which we can choose small \(f,g\) from \(D_{Z^{N},\sigma}\) (\(f,g\text{ mod }q\in R_{q}^{\times}\)) according to the Algorithm 3 in [13], then we can get \(\mathbf{B}_{h,q}=(h,1)\in\mathbf{R}_{q}^{1\times 2}\), \(h=gf^{-1}\). Thus, the SIS problem means to search \(\boldsymbol{\zeta}_{1},\boldsymbol{\zeta}_{2}\) meeting \(\mathbf{B}_{h,q}(\boldsymbol{\zeta}_{1},\boldsymbol{\zeta}_{2})^{T}=0\text{ mod }q\), and \(||(\boldsymbol{\zeta}_{1},\boldsymbol{\zeta}_{2}||\leq\beta\)._  
Gaussian sampling was used for constructing the trapdoor in [29], i.e., a short basis was used to construct the trapdoor without revealing anything about this basis. Figure 2: Blind authentication in e-voting system. **Definition 3** (Discrete Gaussian Distribution). : _for \(\forall s>0\), \(x\in\mathbb{R}^{N}\), and the center of Gaussian distribution \(c\), the N-dimensional Gaussian function can be defined as \(\rho_{s,c}(x)=exp(\frac{-\pi||x-c||^{2}}{g^{2}})\). Then the discrete Gaussian distribution on \(\mathcal{L}\) can be defined as \(D_{\mathcal{L},s,c}(x)=\frac{\rho_{s,c}(x)}{p_{c,c}(\mathcal{L})}\)._  
Given real \(\psi>0\), negligible probability \(\psi(n)\), a lattice \(\mathcal{L}\), and its smoothing parameter \(\eta_{e}(\mathcal{L})\leq\sqrt{log(2N/(1+1/e))/\Pi}/\lambda_{1}^{\infty}( \mathcal{L}^{*})\), there always exists \(\psi(n)\) for \(\eta_{e}(\mathcal{L})\leq\omega(\sqrt{logN})/\lambda_{1}^{\infty}(\mathcal{L }^{*})\) given any \(\omega(\sqrt{logN})\) function. If \(s>\eta_{e}(\mathcal{L})\), then the total Gaussian measure on all the kinds of translation of the lattice is the same according to Lemma 2.7 in [29]. If \(s>2\eta_{e}(\mathcal{L})\), then \(D_{\mathcal{L},s,c}(x)\leq(1+e)2^{-N}/(1-e)\). If \(e<\frac{1}{3}\), then the min-entropy of \(D_{\mathcal{L},s,c}(x)\) is at least \(N-1\) according to Lemma 2.10 in [29]. **Lemma 1**. : _The two events occur with probability \(pr[y\gets D_{\sigma}^{1}:||y||\geq 12\sigma]<2^{-100}\) (\(\sigma>0\)), \(pr[y\gets D_{\sigma}^{m}:||y||\geq 2\sigma\sqrt{m}]<2^{-m}\) (\(m\) is a non-negative integer) according to Lemma 3.3 in [14].