An Identity-Based Anti-Quantum Privacy-Preserving Blind Authentication in Wireless Sensor Networks

Abstract

With the development of wireless sensor networks, IoT devices are crucial for the Smart City; these devices change people’s lives such as e-payment and e-voting systems. However, in these two systems, the state-of-art authentication protocols based on traditional number theory cannot defeat a quantum computer attack. In order to protect user privacy and guarantee trustworthy of big data, we propose a new identity-based blind signature scheme based on number theorem research unit lattice, this scheme mainly uses a rejection sampling theorem instead of constructing a trapdoor. Meanwhile, this scheme does not depend on complex public key infrastructure and can resist quantum computer attack. Then we design an e-payment protocol using the proposed scheme. Furthermore, we prove our scheme is secure in the random oracle, and satisfies confidentiality, integrity, and non-repudiation. Finally, we demonstrate that the proposed scheme outperforms the other traditional existing identity-based blind signature schemes in signing speed and verification speed, outperforms the other lattice-based blind signature in signing speed, verification speed, and signing secret key size.

1. Introduction

With the development of wireless sensor networks, Internet of Things (IoT) devices play an important role in smart cities. IoT devices in e-payment and e-voting services are crucial for modernisation [1,2,3]. Meanwhile, a large amount data generated by these IoT devices face the threats of security and privacy leakage since the state-of-art authentication protocols in e-payment and e-voting systems can be attacked by quantum computers successfully [4], i.e., in e-payment and e-voting systems, blind signature (BS) is crucial to protect user privacy and guarantee trustworthy of big data in the cloud  [5,6,7,8]. However, these schemes based on traditional number theory can be attacked successfully by quantum computer.

BS was firstly introduced by Chaum. Then many BS schemes based on number theory were proposed [9], which can be presented as follows:

The first factoring BS scheme based on RSA was proposed by Chaum, this scheme can guarantee the security of payer. However, they did not prove its security. Later, Bellare et al. defined the hard problem of RSA formally. Based on it, they proved the security of Chaum’s scheme. Then a novel proven-secure RSA scheme was proposed by Camenisch and Koprowski etc., it was secure in the standard model. However, these schemes have to use long keys to guarantee security.

In order to overcome the shortages of factoring BS schemes, BS schemes based on discrete logarithm problem (DLP) were proposed for their short keys and high security. Chaum et al. proposed an e-wallet. Later, Okamoto proposed a BS scheme based on DLP. However, these schemes were not proven secure and only satisfy blindness. Then Pointcheval et al. initially considered the property of unforgeability.

After that, researchers were interested in constructing provably-secure BS schemes based on bilinear pairing. Boldyreva proposed a BS scheme based on GDH assumption, this scheme outperformed the other existing schemes in attribution and efficiency. Later, Okamoto proposed a BS scheme based on 2SDH assumption, which is stronger than SDH assumption. However, their efficiency is low.

Meanwhile, all the schemes outlined above need to depend on Public Key Infrastructure (PKI). In order to simplify key management of PKI, an identity-based signature scheme (IDS) was firstly presented by Shamir. In an IDS scheme, given a user’s identity, his public key can be easily obtained. Also, his private key can be obtained easily. Until 2001, Boneh et al. initially proposed an IDS scheme, it has high efficiency, its security is dependent on the bilinear pairing problem. Then some new IDS schemes based on pairing were proposed by researchers. After that, combining BS with identity-based signature, Zhang et al. initially presented an identity-based BS (IDBS) scheme, its security is based on hard problem of bilinear pairing, this scheme was secure and efficient. Unfortunately, its computation cost was too high. Later, a new IDBS based on DLP was presented, the running time and signature size of their scheme [10] were significantly improved. However, these schemes still face the threat of quantum computer attack [4].

Thus, the replaceable IDBS schemes are based on lattice for their high-efficiency and sufficiently secure to quantum computer attack [11,12]. In the paper, a lattice-based IDBS scheme is proposed by using the advantages of number theory research unit lattice (NTRU) such as high efficiency, extremely tight keys, and sufficient safety once properly parameterized.

(1)

Inspired by [13,14,15], we propose a new IDBS scheme on NTRU Lattice (named IDBS-NTRU), which can be secure to resist quantum computer attack.

(2)

We evaluate our IDBS-NTRU’s security. We demonstrate that the proposed scheme is secure. Then we prove that the proposed scheme satisfies confidentiality, integrity, and non-repudiation.

(3)

We compare our IDBS-NTRU’s performance with the other IDBS schemes.

• Comparing with existing traditional IDBS schemes, its signing speed is faster than other schemes, its moves are shorter than other schemes, its signing secret key, and signature size are larger than other schemes.
• Comparing with existing lattice-based BS schemes, its signing speed is faster than other lattice-based BS schemes, its moves are shorter than Rückert and ZM schemes, its signing secret key is smaller than other lattice-based schemes, and its signature length is smaller than Rückert scheme.

Organization. Section 2 presents the definitions of NTRU lattice and IDBS. Section 3 shows how to design an IDBS scheme. Section 4 proves the proposed IDBS’s security, and compares with the existing IDBS schemes in terms of performance. Lastly, we conclude the paper in Section 5.

2. Preliminaries

2.1. The Applications for BS

With the development of big data, which has the properties of volume, variety, velocity, value, veracity, variability, viscosity, and virality, organizations deploy their services such as e-payment and e-voting systems etc. to the cloud [16,17,18]. In e-payment and e-voting systems, BS scheme plays an important role for that BS scheme can protect user’s anonymous instead of encrypting all the data and searching on the ciphertexts [19,20,21]. In addition, scholars proposed some methods to protect security in the cloud [22,23,24,25], which can provide us with new methods to make our scheme in practice. Meanwhile, scholars proposed some methods to detect complex event analysis, which can be used to improve the security of these services and applications in the cloud [26,27]. We will briefly describe e-payment and e-voting systems as follows:

E-payment system: A, B, T, and $Ba$ are denoted as buyer, merchandiser, trusted third party, and bank respectively. Then the e-payment process is presented in Figure 1 [4]. In the beginning, T will produce and deliver keys for all the $Ba$s, $A,B$ will open a new account from their $Ba$ respectively. The details are as follows:

A logins into his account, draws e-cash m from the $Ba$-A, blinds m by using blind factor f, and then obtains $m^{{}^{\prime }}$. The $Ba$-A signs on $m^{\prime }$, and sends the signature ${\sigma }^{\prime }$ to A [28]. A unblinds the signature by using f and obtains $\sigma$. A sends the tuple $<m,\sigma >$ to B. B verifies whether it is valid or not, if it is, he sends the tuple to $Ba$-B. The $Ba$-B deposits the money on B’s account.

E-voting system: the voter, registrar, administrator, tallier, nominators, and validator are denoted as $vo$, $re$, $ad$, $ta$, $no$, and $va$ respectively. The protocol is presented in Figure 2 [4]:

$vo$ sends his id to a $re$, the $re$ checks whether the $vo$ is valid. If he is, the $vo$ can send two $nos$ to $ad$, the $ad$ will check whether they are valid. If they are, the $vo$ can choose a ballot m, blind it by using blind factor f, and then get the blinded message $m^{\prime }$. $m^{\prime }$ will be sent to a $va$, the $va$ signs on it and sends the signature ${\sigma }^{\prime }$ to the $vo$. The $vo$ unblinds ${\sigma }^{\prime }$ by using blind factor f, and gets a signature $\sigma$. The $vo$ sends $m,\sigma$ to a $ta$, the $ta$ will count all his ballots and store the results to a voting database.

2.2. 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\left[x\right]/(x^N+1)$ as a ring. We denote $f={\mathsf{\Sigma }}_{i=0}^{N-1}{f}_i{x}^i$ and $g={\mathsf{\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 $\left|\right|\alpha \left|\right|$ as $\alpha$’s Euclidean norm. We write $R_q=Z_q\left[x\right]/(x^N+1)$ as the ring. We denote polynomial multiplication and concatenation as $f,g$ 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 \mathit{R}$, $h=e\times d^{-1}$ mod q. Then ${\mathcal{L}}_{h,q}=\{u,v\in R^2:u+v\times h=0$ mod $q\}$ is defined as NTRU Lattice. Meanwhile, ${\mathcal{L}}_{h,q}$ is a ${\mathit{R}}^{2N}$ full-rank lattice $\left(\begin{array}{cc}-C\left(h\right)& I\\ qI& O\end{array}\right)$ , in which I is a unit matrix, O is a null matrix, $C\left(h\right)$ is a matrix as follows: $\left(\begin{array}{ccc}{h}_0& h_1\dots & 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,\beta }^{\kappa }$ on NTRU lattice). in a ring $\mathit{R}=Z\left[x\right]/(x^N+1)$, κ is denoted as a distribution, in which we can choose small $f,g$ from ${\mathit{D}}_{Z^N,\sigma }$ ($f,g$ mod $q\in {\mathit{R}}_q^{\times }$) according to the Algorithm 3 in [13], then we can get ${\mathit{B}}_{h,q}=(h,1)\in {\mathit{R}}_q^{1\times 2}$, $h=g{f}^{-1}$. Thus, the SIS problem means to search ${\zeta }_1,{\zeta }_2$ meeting ${\mathit{B}}_{h,q}{({\zeta }_1,{\zeta }_2)}^T=0$ mod q, and $\left|\right|({\zeta }_1,{\zeta }_2||\le \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.

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}\left(x\right)=exp(\frac{-\pi \left|\right|x-{c\left|\right|}^2}{s^2})$. Then the discrete Gaussian distribution on $\mathcal{L}$ can be defined as $D_{\mathcal{L},s,c}\left(x\right)=\frac{{\rho }_{s,c}\left(x\right)}{{\rho }_{s,c}\left(\mathcal{L}\right)}$.

Given real $\psi >0$, negligible probability $\psi \left(n\right)$, a lattice $\mathcal{L}$, and its smoothing parameter ${\eta }_{ϵ}\left(\mathcal{L}\right)\le \sqrt{log(2N/(1+1/ϵ\left)\right)/\Pi }/{\lambda }_1^{\infty }\left({\mathcal{L}}^{\ast }\right)$, there always exists $\psi \left(n\right)$ for ${\eta }_{ϵ}\left(\mathcal{L}\right)\le \omega \left(\sqrt{logN}\right)/{\lambda }_1^{\infty }\left({\mathcal{L}}^{\ast }\right)$ given any $\omega \left(\sqrt{logN}\right)$ function. If $s>{\eta }_{ϵ}\left(\mathcal{L}\right)$, 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 }_{ϵ}\left(\mathcal{L}\right)$, then $D_{\mathcal{L},s,c}\left(x\right)\le (1+ϵ)2^{-N}/(1-ϵ)$. If $ϵ<\frac{1}{3}$, then the min-entropy of $D_{\mathcal{L},s,c}\left(x\right)$ is at least $N-1$ according to Lemma 2.10 in [29].

Lemma 1.

The two events occur with probability $pr[y\leftarrow D_{\sigma }^1:\left|\right|y\left|\right|\ge 12\sigma ]<2^{-100}$ ($\sigma >0$), $pr[y\leftarrow D_{\sigma }^m:\left|\right|y\left|\right|\ge 2\sigma \sqrt{m}]<2^{-m}$ (m is a non-negative integer) according to Lemma 3.3 in [14]. Let $\mathit{B}$ be a basis of $\mathcal{L}$, $\sigma ,c$ be the standard deviation and the center of Gaussian distribution respectively. We can get the desired vectors from the discrete Gaussian sampling algorithm in Algorithm  1.

Algorithm 1$Gausssian(B,\sigma ,c)$.

1: Input: B, $\sigma >0$, c 2: Output: v 3: $v_n\leftarrow 0$ and $c_n\leftarrow c$. 4: for($i\leftarrow N$ to 1) 5:  (a) $c_i^{{}^{\prime }}=<c_i,\widetilde{b_i}>/\left|\right|\widetilde{b_i}{\left|\right|}^2$ 6:  (b) choose $z_i\sim D_{Z^N,s_i^{{}^{\prime }},c_i^{{}^{\prime }}}$ 7:  (c) $c_{i-1}\leftarrow c_i-z_i{b}_i$ and $v_{i-1}\leftarrow v_i+z_i{b}_i$ 8:  end for 9: return $v_0$

Next, we begin to introduce the Rejection-sampling. In a signature scheme, rejection sampling can make the output signature distribution not depend on the signing key.

Theorem 1.

[Rejection Sampling Theorem] V is the subset of $Z^m$, the norms of V’s elements are less than T, $\sigma =\omega \left(T\sqrt{logm}\right)$ is the element in R, M is a constant, $h:V\to R$ is a probability distribution. There are two algorithms. One algorithm is such that $x\leftarrow h,y\leftarrow D_{v,\sigma }^m,outputs(x,y)$ with probability $min(\frac{D_{\sigma }^m\left(y\right)}{M{D}_{v,\sigma }^m\left(y\right)},1)$. The other algorithm is such that $x\leftarrow h,y\leftarrow D_{\sigma }^m,outputs(x,y)$ with probability $\frac{1}{M}$. Then the first algorithm’ distribution does not exceed the second algorithm’s statistical distance $\frac{2^{-\omega \left(logm\right)}}{M}$. Meanwhile, the first algorithm outputs something with probability at least $\frac{1-2^{-\omega \left(logm\right)}}{M}$.

In particular, when $\sigma =\alpha T,\alpha$ is positive, then $M=e^{\frac{12}{\alpha }+\frac{1}{2{\alpha }^2}}$, the first algorithm’s distribution does not exceed the second algorithm’ statistical distance $\frac{2^{-100}}{M}$. The first algorithm outputs something with probability at least $\frac{1-2^{-100}}{M}$.

2.3. IDBS

An IDBS scheme consists of four algorithms $(S{T}_{\epsilon },E{X}_{\epsilon },S{G}_{\epsilon },V{F}_{\epsilon })$, $\mathcal{U}$, $\mathcal{S}$, and $\mathcal{V}$ are denoted as user, signer, and verifier respectively. Master key, master public key, and master private key are severally written as $mk$, $mpk$, and $msk$. System parameters are denoted as $params$, n is the security parameter. The definition is described as follows.

• $S{T}_{\epsilon }\left(1^n\right)$: after inputting n, this algorithm outputs $params$ and $mk$, which contains $mpk$ and $msk$.
• $E{X}_{\epsilon }(params,msk,id)$: after inputting $params$, $msk$, $id$, this algorithm outputs private key $s{k}_{id}$ related to $id$.
• $S{G}_{\epsilon }(id,m,s{k}_{id})$: $\mathcal{U}$ interacts with $\mathcal{S}$ as follows:

  (1)

  $\mathcal{U}$ blinds the message m to $m^{{}^{\prime }}$ by using blind factor, then sends $m^{{}^{\prime }}$ to $\mathcal{S}$.

  (2)

  $\mathcal{S}$ signs on $m^{{}^{\prime }}$ and sends the signature ${\sigma }^{{}^{\prime }}$ to $\mathcal{U}$.

  (3)

  $\mathcal{U}$ unblinds ${\sigma }^{{}^{\prime }}$ and gets $\sigma$. The signature tuple is $(m,\sigma )$.

• $V{F}_{\epsilon }(params,id,m,\sigma )$: this algorithm returns true if $\sigma$ is valid, otherwise returns false.

Before introducing the security properties of IDBS, we define some notations firstly. $\mathsf{\Gamma }$ is denoted as an adversary, U is nonmalicious users, m is the plaintext message, $c,n$ are denoted as a constant and a big integer respectively, $\eta$ is a negligible probability, t is the time.

IDBS should achieve two properties, which are defined as follows [30,31]:

Blindness [32]: $\mathsf{\Gamma }$ chooses two messages $m_0,m_1$, then a random bit i is selected, $m_0,m_1$ are randomly denoted as $m_i,m_{1-i}$, $m_i,m_{1-i}$ are the inputs of two honest users respectively. $\mathsf{\Gamma }$ plays the Experiment 1 with these two users, ${\sigma }_i,{\sigma }_{1-i}$ are the outputs of them respectively. ${\sigma }_i,{\sigma }_{1-i}$ are dispatched to $\mathsf{\Gamma }$, after that, $\mathsf{\Gamma }$ will output a bit $p\in \{0,1\}$. Finally, the probability of $p=i$ is denoted as $\left|Pr\right[p=i]-1/2|<\eta \left(n\right)$. i.e., if no $\mathsf{\Gamma }$ can win the Experiment 1 at the minimum with $\eta$ in t, then it satisfies blindness.

One-more unforgeability  [4]: after $\mathsf{\Gamma }$ interacts with a nonmalicious signer for l times, he tries to forge the $l+1$ valid signature with $\eta$. The game is defined in Experiment 2. i.e., if $\mathsf{\Gamma }$ cannot win the Experiment 2 with $\eta$ at most ${\tau }_1,{\tau }_2,{\tau }_3$ times respectively for extraction, hash, and signature oracles in t, then the scheme satisfies one-more unforgeability.

Experiment 1$Exp{t}_{{\mathcal{S}}^{\ast }}^{bd}\left(n\right)$.

$i{\in }_{\$}\{0,1\}$ $(params,msk)\leftarrow ST\left(1^n\right)$ $s{k}_{id}\leftarrow EX(params,id,msk)$ $(m_0,m_1,stat{e}_{find}){\leftarrow }_{\$}{\mathcal{S}}^{\ast }(find,s{k}_{id},id)$ $stat{e}_{issue}{\leftarrow }_{\$}{\mathcal{S}}^{\ast <.,\mathcal{U}{(id,m_i)}^1>,<.,\mathcal{U}{(id,m_{1-i})}^1>}(issue,stat{e}_{find})$ ${\delta }_i$, ${\delta }_{1-i}$ are respectively $\mathcal{U}(id,m_i),\mathcal{U}(id,m_{1-i})$’s outputs if${\delta }_0\ne fail$ and ${\delta }_1\ne fail$ then  $p{\leftarrow }_{\$}{\mathcal{S}}^{\ast }(guess,{\delta }_0,{\delta }_1,stat{e}_{issue})$ else  $p{\leftarrow }_{\$}{\mathcal{S}}^{\ast }(guess,fail,fail,stat{e}_{issue})$ end if return true iff $p=i$

Experiment 2$Exp{t}_{{\mathcal{U}}^{\ast }}^{omf}\left(n\right)$.

$(params,msk)\leftarrow ST\left(1^n\right)$ $s{k}_{id}\leftarrow EX(params,id,msk)$ $\{(m_1,s_1),...,(m_k,s_k)\}{\leftarrow }_{\$}{\mathcal{U}}^{\ast h(.),<\mathcal{S}\left(s{k}_{id}\right),.{>}^{\infty }}\left(id\right)$ l is the successful interaction number between ${\mathcal{U}}^{\ast }$ and signer return true iff    $m_i\ne m_j$ for $1\le i<j\le k$ and    $VF(m_i,s_i,id)=1$ and    $l+1=k$

3. Proposed IDBS-NTRU Scheme

Most IDBS schemes are designed with the traditional number theorem; these schemes cannot defeat a quantum computers attack. So the replaceable IDBS schemes are based on lattice. Meanwhile, NTRU-cryptosystems have some advantages, such as high-efficiency, extremely tight keys, and sufficient safety after properly parameterized. Therefore, we choose the NTRU lattice to construct a novel IDBS scheme so that we can achieve both security and efficiency.

In this section, we will firstly introduce how to construct an IDBS scheme on NTRU lattice, then we design an e-payment protocol using our proposed scheme.

3.1. IDBS-NTRU Scheme

In this section, we propose our IDBS scheme $\epsilon =(S{T}_{\epsilon },E{X}_{\epsilon },S{G}_{\epsilon },$$V{F}_{\epsilon })$. Let $\mathcal{U}$, $\mathcal{S}$, $\mathcal{V}$ be a user, a signer, and a verifier respectively, N and $id$ be security parameter and user’s identity respectively, $\tilde{\mathsf{\Omega }}(.)$ and $Poly\left(N\right)$ be the asymptotic lower bound and N’s polynomial function respectively [13].

(1)

$S{T}_{\epsilon }\left(1^N\right)$ outputs $(params=(q,\epsilon ,s),mk=(sk,pk\left)\right)$, in which $q=Poly\left(N\right)$, $\epsilon \in (0,\frac{lnN}{lnq})$, and $s=\tilde{\mathsf{\Omega }}\left(N^{\frac{3}{2}}\sigma \right)$. If $N>2$, then $\sigma =N\sqrt{(ln(8Nq)}{q}^{\frac{1}{2}+\epsilon }$, $q^{1/2-\epsilon }=\tilde{\mathsf{\Omega }}\left(n^{\frac{7}{2}}\right)$. If $N=2$, then $\sigma =\sqrt{Nln\left(8Nq\right)}{q}^{\frac{1}{2}+\epsilon }$, $q^{\frac{1}{2}-\epsilon }=\tilde{\mathsf{\Omega }}\left(N^3\right)$. $mk$ is generated as follows [13]:

The algorithm samples $f,g$ from ${\mathit{D}}_{Z^N,s}$, which satisfy $f,g$ $mod$ $q\notin {\mathit{R}}_q^{\times }$. Meanwhile, $\left|\right|f\left|\right|,\left|\right|g\left|\right|\le \sigma \sqrt{N}$ and $<f,g>\in R$. Then the algorithm computes $F_1,G_1\in R$, which satisfy $f{G}_1-g{F}_1=1$. We compute $F_q=q{F}_1,G_q=q{G}_1$, and then obtain ($F,G$) by using babai algorithm in [11], which satisfies $(F,G)=(F_q,G_q)-k(f,g)$, $k\in R$. If $\left|\right|(F,G)\left|\right|\le N\sigma$, then outputs sk = $\mathit{D}$=$\left(\begin{array}{cc}C\left(f\right)& C\left(g\right)\\ C\left(F\right)& C\left(G\right)\end{array}\right)$ and $pk=h=g{f}^{-1}\in {\mathit{R}}_q^{\times }$.

(2)

$E{X}_{\epsilon }(params,id,sk)$ computes $t\leftarrow H\left(id\right)$, and $s{k}_{id}=(s_1,s_2)\leftarrow \left[\right(t,0)$$-Gausssian(sk,\sigma ,(t,0\left)\right)]$, in which $s_1+s_2\ast h=t$. Then the algorithm outputs $s{k}_{id}$ to user $id$ [13].

(3)

$S{G}_{\epsilon }$: Let $m\in {\{0,1\}}^{\ast }$ be the plaintext, $\mathcal{U}$ randomly selects ${\mathit{y}}_1,{\mathit{y}}_2,\mathit{\alpha },\mathit{\gamma }\in {\mathit{D}}_{Z^N,s}$, then $\mathcal{U}$ executes BS protocol in Figure 3.

• $\mathcal{U}$ computes

  $$\begin{array}{c}\hfill \mathit{e}=H^{{}^{\prime }}({\mathit{y}}_1+h{\mathit{y}}_2+h\gamma +\mathit{\alpha }-\mathit{\alpha }H\left(id\right)),m)\end{array}$$

  (1)

  and

  $$\begin{array}{c}\hfill {\mathit{e}}^{\ast }=\mathit{e}-\mathit{\alpha }\end{array}$$

  (2)

  then $\mathcal{U}$ sends $e^{\ast }$ to $\mathcal{S}$.
• $\mathcal{S}$ computes Equations (3) and (4), then sends ${\zeta }_1^{\ast },{\zeta }_2^{\ast }$ to $\mathcal{U}$.

  $$\begin{array}{c}\hfill {\zeta }_1^{\ast }={\mathit{y}}_1+s_1{\mathit{e}}^{\ast }\end{array}$$

  (3)

  $$\begin{array}{c}\hfill {\zeta }_2^{\ast }={\mathit{y}}_2+s_2{\mathit{e}}^{\ast }\end{array}$$

  (4)
  Here, we will explain how to use the rejection sampling theorem, Theorem 1 from Section 2.2. The core idea of this theorem is to make ${\zeta }_1,{\zeta }_2,{\mathit{e}}^{\ast }$ do not rely on the private key $s_1,s_2$ respectively. Our target is that the distribution of ${\zeta }_1,{\zeta }_2$ will obey the distribution $D_{\sigma }^N$. However, ${\zeta }_1,{\zeta }_2$ obey the distribution $D_{v,\sigma }^N$, where $c=v_1$ or $v_2$, ${\mathit{v}}_1=s_1{\mathit{e}}^{\ast }$, and ${\mathit{v}}_2=s_2{\mathit{e}}^{\ast }$. After we appropriately choose a certain M and $\sigma$, the algorithm will approximately output a signature tuple with probability $1/M$, whose distribution is approximate to the distribution where ${\zeta }_1,{\zeta }_2$ are chosen from $D_{\sigma }^N$ [14].
• Finally, $\mathcal{U}$ gets the signature tuple <$m,{\zeta }_1,{\zeta }_2,\mathit{e},id$> from Equations (5) and (6) with probability $min(\frac{D_{Z^N,s}}{M{D}_{Z^N,s,s{k}_{id}{e}^{\ast }}},1)$, in which M is a constant.

  $$\begin{array}{c}\hfill {\mathit{\zeta }}_1={\mathit{\zeta }}_1^{\ast }+\mathit{\alpha }\end{array}$$

  (5)

  $$\begin{array}{c}\hfill {\mathit{\zeta }}_2={\mathit{\zeta }}_2^{\ast }+\mathit{\gamma }\end{array}$$

  (6)

(4)

$V{F}_{\epsilon }(m,\mathit{e},{\mathit{\zeta }}_1,{\mathit{\zeta }}_2,id)$: $\mathcal{V}$ validates whether Equations (7) and (8) is true. If it is, accept it. Otherwise reject it.

$$\begin{array}{c}\hfill \left|\right|({\mathit{\zeta }}_1,{\mathit{\zeta }}_2)\left|\right|\le 4s\sqrt{2N}\end{array}$$

(7)

$$\begin{array}{c}\hfill H^{{}^{\prime }}(h\ast {\mathit{\zeta }}_2+{\mathit{\zeta }}_1-H\left(id\right)\ast \mathit{e},m)=\mathit{e}\end{array}$$

(8)

3.2. An E-Payment Protocol

In this section, we design an e-payment protocol based on NTRU-IDBS scheme, which plays an important role in e-commerce. We will still follow the notations in Section 2.1. As described in Figure 4, A’s account belongs to $bankA$, B’s account belongs to $BankB$. Firstly, A draws e-money from $BankA$. Secondly, A pays the money to B. Finally, B deposits the money to $BankB$. Following is the details:

(1)

T produces and sends keys

• T runs the algorithm $S{T}_{ϵ}$ and produces the system parameter $params$ and master key $mk$.
• T runs algorithm $E{X}_{ϵ}$ and generates the keys for $BankA$ and $BankB$.
• $BankA$’s public key and private key are $i{d}_{BankA},s{k}_{BankA}$ respectively.
• $BankB$’s public key and private key are $i{d}_{BankB},s{k}_{BankB}$ respectively.
• T distributes the corresponding private keys to $BankA$ and $BankB$.

(2)

user opens an account from Bank

• A and B open an account using their real identity, such as passport, ssn, address, email, male, age, and so on, their banks will give them their account information respectively.

(3)

A draws e-money from $BankA$

• A send their account information to $BankA$.
• $BankA$ will verify whether he is a valid user. If it is, continue. Otherwise, abort.
• A wants to draw money m, he will randomly choose vectors ${\mathit{y}}_1,{\mathit{y}}_2,\mathit{\alpha },\mathit{\gamma }$, computes $\mathit{e}=H^{{}^{\prime }}({\mathit{y}}_1+h{\mathit{y}}_2+h\mathit{\gamma }+\mathit{\alpha }-\mathit{\alpha }H\left(id\right),m)$ and ${\mathit{e}}^{\ast }=\mathit{e}-\mathit{\alpha }$ to obtain ${\mathit{e}}^{\ast }$.
• A sends m with the blinded note ${\mathit{e}}^{\ast }$ to $BankA$.
• $BankA$ computes ${\mathit{\zeta }}_1^{\ast }={\mathit{y}}_1+s_1{\mathit{e}}^{\ast }$, ${\mathit{\zeta }}_2^{\ast }={\mathit{y}}_2+s_2{\mathit{e}}^{\ast }$ for ${\mathit{e}}^{\ast }$, and generates the signatures ${\mathit{\zeta }}_1^{\ast }$ and ${\mathit{\zeta }}_2^{\ast }$, then records on the account of A.
• Next, the bank returns ${\mathit{\zeta }}_1^{\ast },{\mathit{\zeta }}_2^{\ast }$ to A.
• A computes ${\mathit{\zeta }}_1={\mathit{\zeta }}_1^{\ast }+\mathit{\alpha }$ and ${\mathit{\zeta }}_2={\mathit{\zeta }}_2^{\ast }+\mathit{\gamma }$ to get ${\mathit{\zeta }}_1,{\mathit{\zeta }}_2$.

(4)

A pays the e-money to B

• A sends $m,\mathit{e},{\mathit{\zeta }}_1,{\mathit{\zeta }}_2,id$ to B.
• B computes $\left|\right|({\mathit{\zeta }}_1,{\mathit{\zeta }}_2)\left|\right|\le 4s\sqrt{2N}$, $H^{{}^{\prime }}(h\ast {\mathit{\zeta }}_2+{\mathit{\zeta }}_1-H\left(id\right)\ast \mathit{e},m)=\mathit{e}$ and checks whether all of them are true. If all are true, accept it, otherwise, reject them.

(5)

B deposits the e-money

• B will send $m,\mathit{e},{\mathit{\zeta }}_1,{\mathit{\zeta }}_2,id$ to $BankB$.
• $BankB$ computes and checks whether $\left|\right|({\mathit{\zeta }}_1,{\mathit{\zeta }}_2)\left|\right|\le 4s\sqrt{2N}$, and $H^{{}^{\prime }}(h\ast {\mathit{\zeta }}_2+{\mathit{\zeta }}_1-H\left(id\right)\mathit{e},m)=\mathit{e}$ are true, if all of them are true, continue; otherwise abort.
• $BankB$ checks whether the e-money is in the list. If it is, abort, otherwise, continue.
• $BankB$ will deposit the e-money on B’s account.
• $BankB$ will send a notice to B that B has received the e-money.
• B will send the goods or receipt to A.

4. Analyzing the Security and Performances

Here, we evaluate our IDBS-NTRU scheme with regard to correctness and security, then we compare the IDBS-NTRU scheme with other IDBS schemes in terms of performance.

4.1. Correctness, Blindness and One-More Unforgeability

Theorem 2 

(Correctness). The IDBS-NTRU scheme is correct.

Proof. 

Following our IDBS-NTRU scheme, we can get

$$\begin{array}{cc}\hfill h& \ast {\mathit{\zeta }}_2+{\mathit{\zeta }}_1-H\left(id\right)\ast \mathit{e}\hfill \\ & =h({\mathit{\zeta }}_2^{\ast }+\gamma )+{\mathit{\zeta }}_1^{\ast }+\mathit{\alpha }-H\left(id\right)\ast \mathit{e}\hfill \\ & =h({\mathit{y}}_2+s_2{\mathit{e}}^{\ast }+\gamma )+{\mathit{y}}_1+\mathit{\alpha }+s_1{\mathit{e}}^{\ast }-H\left(id\right)\ast \mathit{e}\hfill \\ & ={\mathit{y}}_1+h{\mathit{y}}_2+h\mathit{\gamma }+\mathit{\alpha }-\mathit{\alpha }H\left(id\right)\hfill \end{array}$$

(9)

Thus, $H^{{}^{\prime }}(h\ast {\mathit{\zeta }}_2+{\mathit{\zeta }}_1-H\left(id\right)\ast \mathit{e},m)=\mathit{e}$.

By using Lemmas 2 and 3 in [13], the distributions of ${\mathit{\zeta }}_1^{\ast },{\mathit{\zeta }}_2^{\ast }$ are close to $D_{Z^N,s}$, $\mathit{\alpha },\mathit{\gamma }$ are the vectors from ${\mathit{D}}_{Z^N,s}$. So the probability of $\left|\right|{\mathit{\zeta }}_1\left|\right|,\left|\right|{\mathit{\zeta }}_2\left|\right|\le 4s\sqrt{N}$ is at least $1-2^{-N}$. Then we can get $\left|\right|({\mathit{\zeta }}_1,{\mathit{\zeta }}_2)\left|\right|\le 4s\sqrt{2N}$.

To prove IDBS-NTRU scheme’s blindness, we introduce the statistical distance theorem, that is crucial to prove blindness property. ☐

Theorem 3 

(Statistical Distance Theorem). let random variable number $P,Q\in \mathsf{\Omega }$, in which Ω is a finite domain. The statistical distance equation is presented as below [33]:

$$\begin{array}{c}\hfill \Delta (P,Q)=1/2\sum _{\omega \in \mathsf{\Omega }}|Pr[P=\omega ]-Pr[Q=\omega ]|\end{array}$$

(10)

When we prove IDBS-NTRU’s blindness, the malicious ${\mathcal{S}}^{\ast }$ will play the Experiment 1 with two trust users respectively.

Theorem 4 

(Blindness). The IDBS-NTRU satisfies blindness.

Proof. 

A random bit $i\leftarrow \{0,1\}$ is chosen, which is kept secret from ${\mathcal{S}}^{\ast }$. Then ${\mathcal{S}}^{\ast }$ chooses $m_0,m_1$, then ${\mathcal{S}}^{\ast }$ interacts with two honest users as in Experiment 1. Following is the protocol:

• $(pk,sk)\leftarrow K{G}_{\epsilon }\left(1^k\right)$
• $s{k}_{id}\leftarrow EX(params,id,sk)$
• Under finding mode, ${\mathcal{S}}^{\ast }$ selects $m_0,m_1\leftarrow {\mathcal{S}}^{\ast }(1^k,id,s{k}_{id})$.
• Under issuing mode, a random bit i is selected randomly, that cannot be obtained by ${\mathcal{S}}^{\ast }$. Then $m_0,m_1$ are randomly denoted as $m_i,m_{1-i}$ respectively. ${\mathcal{S}}^{\ast }$ concurrently interacts with $\mathcal{U}(id,m_i)$ and $\mathcal{U}(id,m_{1-i})$ .
• If one user outputs $\delta \left(m_i\right)$, the other outputs $\delta \left(m_{1-i}\right)$, we will send a sequence < $\delta \left(m_i\right),\delta \left(m_{1-i}\right)$> to ${\mathcal{S}}^{\ast }$.
• Under guessing mode, ${\mathcal{S}}^{\ast }$ returns $\tilde{i}$.

As in Figure 3, the Interactive values do not depend on m, so what we need to do is analyzing ${\mathit{e}}^{\ast },{\mathit{y}}_1,{\mathit{y}}_2,{\mathit{\zeta }}_1^{\ast },{\mathit{\zeta }}_2^{\ast }$.

For ${\mathit{e}}^{\ast }$, the statistical-distance is defined as follows

$$\begin{array}{c}\hfill \Delta ({\mathit{e}}_i^{\ast },{\mathit{e}}_{1-i}^{\ast })=1/2\sum _{{\mathit{e}}^{{\ast }^{\prime }}\in D_{Z^N,s}}|Pr({\mathit{e}}_i^{\ast }={\mathit{e}}^{{\ast }^{\prime }})-Pr({\mathit{e}}_{1-i}^{\ast }={\mathit{e}}^{{\ast }^{\prime }})|\end{array}$$

(11)

For $\mathit{\alpha }$ is a random vector from Discrete Gaussian distribution, we can get the follow equations $Pr({\mathit{e}}_i^{\ast }={\mathit{e}}^{{\ast }^{\prime }})$ is close to $1/2^n$, $Pr({\mathit{e}}_{1-i}^{\ast }={\mathit{e}}^{{\ast }^{\prime }})$ is close to $1/2^n$. Therefor, we can get $\Delta ({\mathit{e}}_i^{\ast },{\mathit{e}}_{1-i}^{\ast })$ is close to 0.

Similarly, we can get $\Delta ({\mathit{y}}_1^i,{\mathit{y}}_1^{1-i})$, $\Delta ({\mathit{y}}_2^i,{\mathit{y}}_2^{1-i})$, $\Delta ({\mathit{\zeta }}_1^{i\ast },{\mathit{\zeta }}_1^{1-i\ast })$, and $\Delta ({\mathit{\zeta }}_2^{i\ast },{\mathit{\zeta }}_2^{1-i\ast })$ are close to 0. Therefore, ${\mathcal{S}}^{\ast }$ cannot recognize m from ${\mathit{e}}^{\ast },{\mathit{y}}_1,{\mathit{y}}_2,{\mathit{\zeta }}_1,{\mathit{\zeta }}_2$, i.e., ${\mathcal{S}}^{\ast }$ wins the experiment with probability $1/2+\eta \left(n\right)$. Therefore, we prove the theorem.

Before proving the one-more unforgeability of IDBS-NTRU, we will define some notations as follows:

Let ${\delta }_1,{\delta }_2,{\delta }_3,{\delta }_4$ be simulating the cost functions of H hash, extract oracle, $H^{{}^{\prime }}$ hash, and signature oracles respectively. Let $\eta ,{\eta }^{{}^{\prime }}$ be non-negligible probability, and t be time respectively, $\mathsf{\Theta }$ be a polynomial time algorithm, and $\mathsf{\Gamma }$ be a polynomial time forger. ☐

Theorem 5 

(One-more Unforgeability). If Γ is able to generate a legal signature with η in t, after at most ${\tau }_1,{\tau }_2,{\tau }_3,{\tau }_4$ times queries respectively to H hash, Extract, $H^{{}^{\prime }}$ hash, and signature oracles. Then R-$SI{S}_{q,1,2,\beta }^{\kappa }$ can be solved by Θ with probability at least ${\eta }^{{}^{\prime }}=(1-2^{-\omega \left(logN\right)})\eta$ in time $t^{{}^{\prime }}=t+{\tau }_1^{{\tau }_2}({\tau }_1{\delta }_1+{\tau }_2{\delta }_2)+$${\tau }_3^{{\tau }_4}({\tau }_3{\delta }_3+{\tau }_4{\delta }_4)$.

Proof. 

Assuming an adversary $\mathsf{\Gamma }$ is able to produce an IDBS signature with $\eta$, we can construct $\mathsf{\Theta }$, this algorithm can obtain the solution of R-$SIS$ on the NTRU lattice. The followings are the simulated interactive environment.

ST: $\mathsf{\Theta }$ selects $h\in R_q^{\times }$, $H,H^{{}^{\prime }}$ at random. Then $\mathsf{\Theta }$ computes and sends the public parameters $paras=\{h,H,H^{{}^{\prime }},ϵ,q,s\}$ to the $\mathsf{\Gamma }$.

H oracle Queries: $\mathsf{\Theta }$ will maintains a list $L_h$, in the beginning, the list is mull. Once receiving an $i{d}_i$, $\mathsf{\Theta }$ will inquire $L_h$. If there exists a corresponding hash value $t_i$, $\mathsf{\Theta }$ will return $t_i$. Otherwise $\mathsf{\Theta }$ will return a random value. After that, $\mathsf{\Theta }$ will save $i{d}_i,t_i$ in $L_h$.

H ${}^{\prime }$ oracle Queries: $\mathsf{\Theta }$ maintains a list $L_h^{{}^{\prime }}$, in the beginning, the list is null. Once receiving $m_i,{\mathsf{\Lambda }}_i=y_{1_i}+h{y}_{2_i}+h{\gamma }_i+{\mathit{\alpha }}_i-{\mathit{\alpha }}_{i}H\left(i{d}_i\right)$, we assume $\mathsf{\Theta }$ has already quire H oracle and gotten an entry $i{d}_i,t_i$. Then $\mathsf{\Theta }$ will quire $L_h^{{}^{\prime }}$. If there already exists a corresponding hash value $e_i$, $\mathsf{\Theta }$ will return $e_i$. Otherwise, $\mathsf{\Theta }$ will return a random value. After that, $\mathsf{\Theta }$ will save $m_i,{\mathsf{\Lambda }}_i,y_{1_i},y_{2_i},{\gamma }_i,{\alpha }_i,i{d}_i,e_i,t_i$ to $L_h^{{}^{\prime }}$.

EX Oracle Queries: $\mathsf{\Theta }$ maintains a list $L_{id}$, in the beginning, the list is null. Once receiving an identity $i{d}_i$, $\mathsf{\Theta }$ will inquire H oracle. If there does not exist a corresponding hash value in $L_{id}$, $\mathsf{\Theta }$ will randomly selects a $t_i$ and return it. Otherwise, return the corresponding $t_i$. After that, $\mathsf{\Theta }$ can get a $s{k}_{i{d}_i}=(s_{1_i},s_{2_i})$, $\mathsf{\Theta }$ returns $s{k}_{i{d}_i}$ to $\mathsf{\Gamma }$ as the private key related with $i{d}_i$ and saves the tuple $(i{d}_i,t_i,s{k}_{i{d}_i})$ in $L_{id}$.

SG Oracle Queries: $\mathsf{\Gamma }$ queries the signing oracle for $(m_i,i{d}_i)$. $\mathsf{\Theta }$ checks if $i{d}_i$ is already queried for H, $H^{{}^{\prime }}$ or extraction oracles. If it is, $\mathsf{\Theta }$ can get an entry $(i{d}_i,t_i,s{k}_{i{d}_i})$ from $L_{id}$. Else $\mathsf{\Theta }$ simulates the extraction oracle and obtain a new secret key. Then $\mathsf{\Theta }$ executes the BS protocol to obtain a valid signature $(m_i,i{d}_i,{\mathit{e}}_i,{\mathit{\zeta }}_{1_i},{\mathit{\zeta }}_{2_i})$ and stores the value $(m_i,i{d}_i,{\mathit{e}}_i,{\mathit{\zeta }}_{1_i},{\mathit{\zeta }}_{2_i})$ in the list $L_S$.

Output: Finally, $\mathsf{\Gamma }$ firstly outputs a forged signature $({\mathit{e}}_i,{\mathit{\zeta }}_{1_i},{\mathit{\zeta }}_{2_i},m_i,i{d}_i)$. $\mathsf{\Theta }$ rewinds ${\mathsf{\Gamma }}_i$ to the point where it queries $H^{{}^{\prime }}$ for $(m_i,i{d}_i)$ and obtains another signature $({\mathit{e}}_i^{{}^{\prime }},{\mathit{\zeta }}_{1_i}^{{}^{\prime }},{\mathit{\zeta }}_{2_i}^{{}^{\prime }},m_i,i{d}_i)$.

Therefore, $\mathsf{\Theta }$ can solve R-$SI{S}_{q,1,2,\beta }^{\kappa }$ problem over the NTRU lattice. $\mathsf{\Theta }$ obtains $s{k}_{i{d}_i}$ and ${\mathit{e}}_i^{{}^{\prime }},{\mathit{y}}_{1_i},{\mathit{y}}_{2_i},{\mathit{\alpha }}_i,{\gamma }_i$ from the $L_S$. $\mathsf{\Theta }$ computes ${\mathit{\zeta }}_{1_i}={\mathit{y}}_{1_i}+s_{1_i}\ast {\mathit{e}}_i^{\ast }+{\mathit{\alpha }}_i,{\mathit{\zeta }}_{2_i}={\mathit{y}}_{2_i}+s_{2_i}\ast {\mathit{e}}_i^{\ast }+{\gamma }_i$, and ${\mathit{\zeta }}_{1_i}+{\mathit{\zeta }}_{2_i}\ast h-H\left(i{d}_i\right){\mathit{e}}_i$. Then $\mathsf{\Theta }$ checks whether ${\mathit{\zeta }}_{1_i}+{\mathit{\zeta }}_{2_i}\ast h-H\left(i{d}_i\right){\mathit{e}}_i={\mathit{\zeta }}_{1_i}^{{}^{\prime }}+{\mathit{\zeta }}_{2_i}^{{}^{\prime }}\ast h-H\left(i{d}_i\right){\mathit{e}}_i^{{}^{\prime }}={\mathit{y}}_{1_i}+h\ast {\mathit{y}}_{2_i}+h{\gamma }_i+{\mathit{\alpha }}_i-{\mathit{\alpha }}_{i}H\left(i{d}_i\right)$. If they are not equal, there is a collision of $H^{{}^{\prime }}$. If $({\mathit{\zeta }}_{1_i},{\mathit{\zeta }}_{2_i})\ne ({\mathit{\zeta }}_{1_i}^{{}^{\prime }},{\mathit{z}}_{2_i}^{{}^{\prime }})$, we can get $({\mathit{\zeta }}_{1_i}-{\mathit{\zeta }}_{1_i}^{{}^{\prime }})+h({\mathit{\zeta }}_{2_i}-{\mathit{\zeta }}_{2_i}^{{}^{\prime }})=0$ and $\left|\right|({\mathit{\zeta }}_{1_i}-{\mathit{\zeta }}_{1_i}^{{}^{\prime }},{\mathit{\zeta }}_{2_i}-{\mathit{\zeta }}_{2_i}^{{}^{\prime }})\left|\right|\le 8s\sqrt{2N}$. So $({\mathit{\zeta }}_{1_i}-{\mathit{\zeta }}_{1_i}^{{}^{\prime }},{\mathit{\zeta }}_{2_i}-{\mathit{\zeta }}_{2_i}^{{}^{\prime }})$ is one solution to R-$SI{S}_{q,1,2,\beta }^{\kappa }$.

Now we start to analyze the advantage of $\mathsf{\Theta }$. As discussed above, $\mathsf{\Theta }$ wins the game if and only if $\mathsf{\Gamma }$ has successfully forged $({\mathit{\zeta }}_1^{{}^{\prime }},{\mathit{\zeta }}_2^{{}^{\prime }},{\mathit{u}}^{{}^{\prime }})$ and $({\mathit{\zeta }}_1,{\mathit{\zeta }}_2)\ne ({\mathit{\zeta }}_1^{{}^{\prime }},{\mathit{\zeta }}_2^{{}^{\prime }})$. Next according to the Lemma 4.6 in [34], $\mathsf{\Gamma }$ can solve R-$SI{S}_{q,1,2,\beta }^{\kappa }$ with probability at least ${\eta }^{{}^{\prime }}=(1-2^{-\omega \left(logN\right)})\eta$, where $\beta =8s\sqrt{2N}$. It is obviously that $t^{{}^{\prime }}=t+{\tau }_1^{{\tau }_2}({\tau }_1{\delta }_1+{\tau }_2{\delta }_2)+{\tau }_3^{{\tau }_4}({\tau }_3{\delta }_3+{\tau }_4{\delta }_4)$. We prove this theorem. ☐

4.2. Performances

Here, we will compare our IDBS-NTRU’s performances with other IDBS schemes. First of all, we will compare NTRU-IDBS scheme with traditional IDBS schemes in terms of performance, which were constructed based on number theory. Secondly, we will compare our IDBS-NTRU scheme with lattice-based BS schemes in terms of performance.

(1) Comparing with traditional IDBS schemes

As shown in

Table 1. Performance comparison with traditional IDBS schemes.

IDBS Scheme	ZK  [35]	HCZ [10]	CZYW [36]	Ours
Hard Problem	CDHP	DLP	Factoring	R-SIS
Signing Speed	$O\left(n^3\right)$	$O\left(n^3\right)$	$O\left(n^3\right)$	$O\left(n\right)$
Verifying Speed	$O\left(n^3\right)$	$O\left(n^3\right)$	$O\left(n^3\right)$	$O\left(n\right)$
Moves	3	3	2	2
Signing Secret key	2n	logk+2n	n	$2nlog\left(s\sqrt{n}\right)$
Signature size	3n	logk+4n	n	$2nlog\left(12\sigma \right)+n(log\lambda +1)$

, we compare IDBS-NTRU’performance with ZK scheme [35], HCZ scheme [10], and CZYW scheme [36]. The ZK scheme is constructed based on computational diffie-hellman problem of bilinear pairings. The HCZ scheme is constructed based on discrete logarithm problem of ellipse curve. The CZYW scheme is constructed based on big integer factoring problem. The IDBS-NTRU scheme’s signing speed and verification speed are O(n), which outperform ZK scheme, HCZ scheme, and CZYW schemes. Its moves are 2, it is shorter than ZK scheme and HCZ scheme. Its signing secret key is $2nlog\left(s\sqrt{n}\right)$, it is larger than ZK scheme and HCZ scheme. However, the rsa has to use $O\left(n^3\right)$ to achieve n bits security, the signing secret key of IDBS-NTRU scheme is shorter than CZYW scheme. The signature size of IDBS-NTRU scheme is $2nlog\left(12\sigma \right)+n(log\lambda +1)$, it is larger than ZK, HCZ, and CZYW schemes. For the same reason, it is also shorter than CZYW scheme. The most important of all, the BS schemes based on number theory are considered to be insecure to resist quantum computers attack [4], our IDBS-NTRU scheme is more secure than other three traditional schemes.

(2) Comparing with lattice-based BS schemes

We compare IDBS-NTRU’s performance with GHWX [37], ZTZ [4], Rückert [32], and ZM schemes [38] in

Table 2. Performance Comparison with lattice-based BS schemes.

Lattice-Based BS Scheme	GHWX [37]	ZTZ [4]	Rückert [32]	ZM [38]	Ours
Hard Problem	SIS	CVP	ISVP	SIS	R-SIS
Signing Speed	$O\left(n^2\right)$	$O\left(n^{2}logn\right)$	$O\left(n{\left(logn\right)}^c\right)$	$O\left(n^2\right)$	$O\left(n\right)$
Verifying Speed	$O\left(n^3\right)$	O(n)	O(n)	$O\left(n^3\right)$	O(n)
Moves	2	2	4	3	2
Signing secret key	$nmlog(q+1)$	$d{n}^2(logn+1)$	$mnlog(2d_s+1)$	$m^{2}log(q+1)$	$2n$$log\left(s\sqrt{n}\right)$
Signature size	$mlog(q+1)$	$dn(logn+1)$	$n^2+mn$ $log\left(2mn{d}_s{d}_{{ϵ}^{\ast }}\right)$	$2mlog(q+1)$	$2nlog\left(12\sigma \right)+$ $n(log\lambda +1)$
Identity Based	yes	no	no	yes	yes

, n denotes safety parameter. GHWX scheme and ZM scheme are constructed based on small integer solution problem of lattice. ZTZ scheme is constructed based on closest vector problem of lattice. Rückert is constructed based on ideal-lattice shortest vector problem.

As presented in Table 2, IDBS-NTRU’s signing speed is $O\left(n\right)$, which outperforms all the other schemes. IDBS-NTRU’s verification speed is $O\left(n\right)$, which outperforms GHWX and ZM schemes. Our IDBS-NTRU scheme has two moves, it is shorter than Rückert scheme, and ZM scheme. In Rückert scheme, the parameters satisfy $m>\lfloor c_{m}log\left(1\right)\rfloor +1$, $c_m>1/log\left(2d_s\right)$. In ZM schemes, the parameters satisfy $m>2nlogq,q>2$. The signing secret key of our IDBS-NTRU scheme is $2nlog\left(s\sqrt{n}\right)$, it is shorter than all the other schemes. The signature size of our IDBS-NTRU scheme is $2nlog\left(12\sigma \right)+n(log\lambda +1)$, it is shorter than Rückert scheme, but it is larger than GHWX, ZTZ, and ZM schemes. The ZTZ scheme and Rückert scheme are not identity-based scheme, they depend on the public key infrastructure. However, our IDBS-NTRU scheme does not need to dependent on public key infrastructure.

5. Conclusions

In this work, we present an IDBS-NTRU scheme by using NTRU lattice, this scheme can protect user privacy and guarantee the trustworthy of big data in e-payment and e-voting systems in wireless sensor networks, this scheme has the advantages of NTRU Lattice such as high efficiency, compact key, high security after appropriate parameterized etc. Our scheme is secure and efficient. Furthermore, we prove IDBS-NTRU satisfies blindness and unforgeability. In addition, comparing with traditional IDBS schemes, IDBS-NTRU outperforms other IDBS schemes in terms of signing speed and verifying speed. Comparing with lattice-based schemes, IDBS-NTRU scheme outperforms other schemes in terms of signing speed, verifying speed, and signing secret key, outperforms Rückert scheme in terms of signature size moves and signature size, and outperforms ZM scheme in terms of moves. The schemes based on number theorem are considered insecure to resist the quantum computers attack, so our scheme is more secure than them. Furthermore, lattice-based schemes usually have a lot of parameters which need to be initialized correctly, these schemes are not easy to implement. Therefore, almost all the works related with lattice-based cryptography are still in the step of theory research.

In addition, if we can add some common message such as date between the signer and a user in our scheme, it is easy to transform our scheme into an identity-based partial BS scheme, which is suitable for the real e-payment and e-voting systems. In the future, we will continue to construct a partial IDBS scheme based on lattice.