# Identity-Based Linkable Ring Signature on NTRU Lattice

Authors: Yongli Tang; Feifei Xia; Qing Ye; Mengyao Wang; Ruijie Mu; Xiaohang Zhang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Although most existing linkable ring signature schemes on lattice can effectively resist quantum attacks, they still have the disadvantages of excessive time and storage overhead. This paper constructs an identity-based linkable ring signature (LRS) scheme over NTRU lattice by employing the technologies of trapdoor generation and rejection sampling. The security of this scheme relies on the small integer solution (SIS) problem on NTRU lattice. We prove that this scheme has unconditional anonymity, unforgeability, and linkability under the random oracle model (ROM). Through the performance analysis, this scheme has a shorter size of public/private keys, and when the number of ring members is small (such asN≤8), this scheme has a shorter signature size compared with other existing latest lattice-based LRS schemes. The computational efficiency of signature has also been further improved since it only involves multiplication in the polynomial ring and modular operations of small integers. Finally, we implemented our scheme and other similar schemes, and it is shown that the time for the signature generation and verification of this scheme decreases roughly by 44.951% and 33.503%, respectively.


---

## Body

## 1. Introduction

With the rise in cryptocurrencies represented by Bitcoin in recent years, blockchain [1] technology has attracted widespread attention. It is increasingly being used for electronic voting, medical information sharing, and intellectual property. However, the transmission and storage of data on the blockchain are publicly visible and anyone can access it. Only through the approach of “pseudo-anonymity” to protect the privacy of both parties in the transaction cannot satisfy complete privacy protection requirements. Also, researchers pointed out that ring signature is one of the approaches which are expected to solve this problem.Rivest et al. [2] first proposed ring signature at Asiacrypt 2001. In the ring signature scheme, any ring member can produce a signature by using their own private key and the public keys of all members. The verifier can only identify whether the signature is produced by a ring member and cannot determine which specific member generated the signature. Therefore, ring signature is anonymous and can be widely used in electronic cash, electronic voting, etc. Most ring signatures are designed based upon conventional public key infrastructure (PKI). Under the PKI system, the user’s identity information and public key are bound together by a digital certificate. If the number of ring members is excessive, the management, storage, and verification of certificates will occupy a large amount of system resources and become the bottleneck of the whole system. Shamir [3] constructed an identity-based cryptography to tackle the problems mentioned, in which the public key is calculated by the key generation center (KGC) according to the user’s identity information (e.g., ID number, e-mail address, and so on). Then, the user’s private key is obtained based on the system master secret key (MSK) and public key. KGC no longer needs to manage a series of certificates. Since it improves the computation performance of the system and avoids certificate management, identity-based cryptography has gained wide attention in these years.In 2002, Zhang and Kim [4] proposed the first identity-based ring signature. Subsequently, many such schemes [5–8] have been proposed. Liu et al. [9] incorporated linkability into ordinary ring signatures and constructed the first LRS scheme based upon the discrete logarithm problem (DLP) in 2004. Besides having the anonymity and unforgeability of ordinary ring signatures, LRS can also detect whether the user has completed two or more signatures with the identical private key. When applied to the blockchain, it effectively verifies whether users have double-spending problems while protecting the privacy of blockchain users. Currently, LRS performs a pivotal role in the application domains such as cryptocurrency, electronic elections, and electronic cash [10–12]. Au et al. [13] first designed an identity-based constant-size LRS scheme in 2013, and its security is proved based upon DLP under the ROM. The LRS with unconditional anonymity was given by Liu et al. [14] in the same year, which further improved the security of LRS and made up for the weaknesses of linkability and strong anonymity in ring signature that cannot be realized simultaneously. In 2019, Deng et al. [15] constructed the most efficient identity-based LRS scheme, which requires only seven pairing operations in signature generation and verification. The above schemes are mainly founded on classical number theory problems (e.g., the large integer decomposition [16] and the finite field discrete logarithm problem [17]). These cryptosystems will be breached in polynomial time due to the threats brought by the attacks of quantum computers. Shor [18] pointed that the scheme constructed on the classical number theory problems will no longer be safe in that it cannot effectively resist quantum attacks. If the ring signature is still designed based upon the classical number theory problems, the security of ring signature will be difficult to guarantee in the quantum era.In the course of searching for the replacement of traditional public key cryptography, the public key cryptosystem on lattice is becoming a prominent candidate for anti-quantum attack cryptographic algorithm. Besides, since it mostly involves matrix-vector multiplication and polynomial-polynomial multiplication operations on lattice, compared with the schemes designed on classical number theory problems, the new lattice-based cryptosystem has attracted extensive attention because it has better asymptotic efficiency and parallelization and is resistant to quantum attacks and other merits. In 2010, Rückert [19] first designed an identity-based ring signature over lattice. In 2012, Tian et al. [20] gave an efficient identity-based ring signature on lattice, and the safety is proved under choosing subring and adaptive chosen-message attack, which to some extent could improve the security of this scheme. However, the computational efficiency of the signature is low owing to the large length of the key and signature. Then, other identity-based cryptosystems [21–23] were proposed. In 2017, Yang et al. [24] constructed the first LRS on lattice based on the accumulator, zero-knowledge proof, and weak pseudo-random function. In 2018, Torres et al. [25] designed a lattice-based LRS with unconditional anonymity, and the security of this scheme relies on the hardness of the SIS [26] problem. The signature generation is more efficient because the rejection sampling algorithm is adopted, and this scheme is applied to the confidentiality agreement for promotion. That same year, Baum et al. [27] produced a more efficient LRS scheme based upon the collision-resistance hash function on lattice, whose security is based on the problem of Module-LWE and Module-SIS. In 2020, Beullens et al. [28] gave the logarithmic LRS from isogeny and lattice assumptions; the length of the signature has a logarithmic relationship with the number of ring members. But they generally have the disadvantages of high communication costs and lower computation performance. However, the NTRU lattice is a particular lattice based on the polynomial ring, which attracts wide attention because the signature is designed on the NTRU lattice cryptosystem requiring a shorter size of key and signature, and the efficiency of computational can be improved greatly. In 2019, Lu et al. [29] designed the first practical and efficient LRS based upon the chameleon hash plus (CH+) function on NTRU lattice. The signature length of this scheme is short, and the efficiency of signature generation is further promoted compared with other similar lattice-based schemes.


### 1.1. Our Construction

To decrease the signature length and further promote the efficiency of computation for the LRS scheme, we constructed an identity-based LRS scheme over NTRU lattice, and the architecture of the proposed scheme is shown in Figure1. Our main contributions are as follows. (1) Combining NTRU lattice with identity-based ring signature and adopting the compact Gaussian sampler (CGS) algorithm and rejection sampling techniques to design an identity-based LRS. (2) We proved that the scheme proposed in this paper has unconditional anonymity, unforgeability, and linkability under the ROM. The unforgeability of this scheme relies on the SIS problem over NTRU lattice. (3) The performance analyses in two sides of time costs and storage overhead are provided in detail. It is indicated that this scheme has a smaller size of key and signature, and the computational efficiency of signature generation and verification has also been further increased through the comparison with other similar schemes. Finally, we implemented our scheme and other schemes [15, 28, 29], and it is shown that the time for signature generation and verification of this scheme decreases roughly by 44.951% and 33.503%, respectively, compared with other three existing latest LRS schemes [15, 28, 29]. Compared with latest lattice-based LRS schemes [28, 29], the proposed scheme has the smallest public and private key size and also has the smallest signature size when N≤8.Figure 1
Identity-based linkable ring signature on NTRU lattice.


### 1.2. Organization

The remainder of this paper is structured as follows. At first, we introduce the symbols, NTRU lattice, the NTRU-SIS problem, and some algorithms in Section2. Then, we introduce the definition and security model of identity-based LRS in Section 3. In Section 4, we introduce the proposed scheme. The security analysis of this scheme is shown in Section 5. In Section 6, we discuss how initial parameters are selected and point at the next research directions. In Section 7, we make a detailed performance comparison with other three existing schemes [15, 28, 29]. Finally, we present the experimental results of this scheme and related schemes in Section 8.


## 1.1. Our Construction

To decrease the signature length and further promote the efficiency of computation for the LRS scheme, we constructed an identity-based LRS scheme over NTRU lattice, and the architecture of the proposed scheme is shown in Figure1. Our main contributions are as follows. (1) Combining NTRU lattice with identity-based ring signature and adopting the compact Gaussian sampler (CGS) algorithm and rejection sampling techniques to design an identity-based LRS. (2) We proved that the scheme proposed in this paper has unconditional anonymity, unforgeability, and linkability under the ROM. The unforgeability of this scheme relies on the SIS problem over NTRU lattice. (3) The performance analyses in two sides of time costs and storage overhead are provided in detail. It is indicated that this scheme has a smaller size of key and signature, and the computational efficiency of signature generation and verification has also been further increased through the comparison with other similar schemes. Finally, we implemented our scheme and other schemes [15, 28, 29], and it is shown that the time for signature generation and verification of this scheme decreases roughly by 44.951% and 33.503%, respectively, compared with other three existing latest LRS schemes [15, 28, 29]. Compared with latest lattice-based LRS schemes [28, 29], the proposed scheme has the smallest public and private key size and also has the smallest signature size when N≤8.Figure 1
Identity-based linkable ring signature on NTRU lattice.


## 1.2. Organization

The remainder of this paper is structured as follows. At first, we introduce the symbols, NTRU lattice, the NTRU-SIS problem, and some algorithms in Section2. Then, we introduce the definition and security model of identity-based LRS in Section 3. In Section 4, we introduce the proposed scheme. The security analysis of this scheme is shown in Section 5. In Section 6, we discuss how initial parameters are selected and point at the next research directions. In Section 7, we make a detailed performance comparison with other three existing schemes [15, 28, 29]. Finally, we present the experimental results of this scheme and related schemes in Section 8.


## 2. Preliminaries

### 2.1. Symbol Definition

For the convenience of presentation, the descriptions of the used notations are illustrated in Table1.Table 1
Symbol description.
NotationsExplanationRPolynomial ringR=ℤx/xn+1ℤInteger setRqInteger moduloq polynomial ring Rq=ℤqx/xn+1slFirstl bits of string sAMatricesℤqnn-dimensional vector of modulo q residue class ringℤqn×mn×m-dimensional matrix space of modulo q residue class ringℤmm-dimensional integer vector spacexVectors, assumed to be in column formRmm-dimensional real vector spacex⟵DChooses vectorx from probability distribution DxEuclidean norm of vectorxℝSet of real numbersneglnThe negligible function ofnBesides the symbols in Table1, this paper also uses symbols such as O˜,ω, which are commonly used symbols for computation complexity.


### 2.2. Related Definitions of NTRU Lattice

Definition 1 (convolutional polynomial ring).
Let ringR=ℤx/xn+1; when the addition operation on R remains unchanged and the multiplication operation can be replaced by a convolution operation, then R is called a convolution polynomial ring. Therefore, given a prime number q and a modular convolution polynomial ring Rq=R/qR.
Letf=∑i=0n−1fixi,g=∑i=0n−1gixi∈Rq; then, the two operations on Rq are defined as follows:(1)
Addition operation +:f+g=g=∑i=0n−1fi+giximodq∈Rq.(2)
Convolution operation∗: f∗g=f∗gmodxn+1∈Rq.Definition 2 (anti-circular matrices).
Let polynomialf∈Rq, and the coefficient vector of the polynomial f is f0,f1,…,fn−1; then, the coefficient vector of the polynomial x⋅f is −fn−1,f0,…,fn−2. By analogy, the coefficient vector of the polynomial xn−1⋅f is −f1,−f2,…,f0. That is, the anti-circular matrix Anf is composed of n polynomial vectors formed by successive cyclic shifts of the polynomial f∈Rq. So, the anti-circular matrix Anf can be expressed as a vector. The anti-circular matrix formed by polynomial f is as follows:(1)Anf=f0f1⋯fn−1−fn−1f0⋯fn−2⋮⋮⋯⋮−f1−f2⋯f0=fx∗f⋮xn−1∗f.Definition 3 (NTRU lattice).
n is a security parameter and is a power-of-two integer; let a prime q≥2 and polynomials f,g∈Rq,h=g∗f−1modq, satisfying f is reversible, where f−1∈Rq. Then, the NTRU lattice related to q and h is as follows:(2)Λq,h=u,v∈R2|u+v∗h=0modq.
NTRU latticeΛq,h is a 2n dimension full-rank lattice, Aq,h=−AnhInqIn0n∈ℤq2n×2n is a set of basis matrix of NTRU lattice, and it is uniquely defined by the polynomial h∈Rq. Therefore, the space required to store the basis matrix Aq,h is small. However, in the application of NTRU lattice-based cryptosystem, Aq,h cannot be used as a trapdoor basis because Aq,h has a very large orthogonal defect when the polynomial h∈Rq is uniformly distributed.Definition 4 (discrete Gaussian distribution).
For anyσ>0 and vector c∈Rm, the discrete Gaussian distribution centered on vector c over the lattice Λ is described as follows:(3)DΛ,σ,cx=ρσ,cxρσ,cΛ=ρσ,cx∑x∈Λρσ,cx,∀x∈Λ,where ρσ,cx=exp−πx−c2/σ2.
Whenc=0, the Gaussian distribution on Rm and the discrete distribution on lattice Λ can also be defined as Dσm and DΛ,σm, respectively.Lemma 1.
Given any parameterσ>0 and positive integer m, the following formulas hold [30]:(1)
Prx⟵Dσ1:x>ωσlogm=2−ωlogm.(2)
For any vectorx∈ℤm and σ≥log3m, there is Dσmx≤2−m+1.(3)
Prx⟵Dσm:x>2σm<2−m.


### 2.3. The NTRU-SIS Problems

Definition 5 (the SIS problem on NTRU lattice, NTRU-SIS).
Given parametersn,m,q, polynomial h=g∗f−1modq∈Rq, and a real number β>0, the NTRU-SIS problem is defined as follows: finding two non-zero small polynomials u,v∈Rq2 satisfying u+v∗h=0modq and u,v≤β.
NTRU-SIS Assumption. Given system linear equations of modulo q, without knowing the trapdoor, the advantage of finding two non-zero small polynomials u,v∈Rq2 that meet u+v∗h=0modq and u,v≤β can be neglected for any probabilistic polynomial time (PPT) algorithm.


### 2.4. Related Algorithms

Definition 6 (trapdoor generation algorithm on NTRU lattice).
Given integersn and k, where k>0 and n=2k, and a prime q=1mod2n, let a parameter s=1.17q/2n and f,g,F,G∈R satisfying f⋅F−g⋅G=q. The PPT algorithm TrapGenNTRUq,n,s [31] can output a polynomial h=g∗f−1modq and a set of short basis Bf,g=AngAnG−Anf−AnF∈ℤq2n×2n on NTRU lattice Λh,q.Definition 7 (discrete Gaussian sampling function).
In 2015, Lyubasevsky and Prest [32] proposed the compact Gaussian sampler (CGS) algorithm that can quickly implement discrete Gaussian distribution sampling on NTRU lattice.Theorem 1.
This is a more efficient polynomial time algorithmCGSB,σ,c [32]: on inputting a lattice basis B=b1,b2,…,bn, Gaussian parameter σ, and center vector c∈ℤm, the algorithm CGSB,σ,c can output the sampling z on distribution DΛB,σ,c.Lemma 2.
Let a parameterσ≥B⋅1/π1/2ln2+2/ε, where ε<2−λ/4n,log2n<λ<qn/2, such that the statistical distance between the output of CGSB,σ,c and the distribution DΛB,σ,c is no more than 2−λ.Definition 8 (rejection sampling).
In 2012, Lyubasevsky [30] proposed the rejection sampling and, based on this technology, first designed the signature scheme without trapdoor on the lattice. This technology can be applied to the signature system, which obtains the signature with a definite probability and makes the distribution of the signature and private key separate from one another so that the signature private key can be effectively prevented from leaking. The conclusions are as follows.Lemma 3.
For anyv∈ℤm,σ=ωvlogm, we have PrDσmz/Dv,σmz=O1:z⟵Dσm=1−2−ωlogm.Theorem 2.
LetV=v∈ℤm:v<t,σ=ωtlogm,h:V⟶ℝ be a probability distribution; for any constant M=O1, the statistical distance of output distribution between Algorithm 1 and Algorithm 2 is less than 2−ωlogm/M.Algorithm 1.
v⟵h;z⟵Dv,σm: output z,v with the probability of minDσmz/MDv,σmz,1.Algorithm 2.
v⟵h;z⟵Dσm: output z,v with the probability of 1/M.
Furthermore, the output probability of Algorithm1 is at least 1−2−ωlogm/M.


## 2.1. Symbol Definition

For the convenience of presentation, the descriptions of the used notations are illustrated in Table1.Table 1
Symbol description.
NotationsExplanationRPolynomial ringR=ℤx/xn+1ℤInteger setRqInteger moduloq polynomial ring Rq=ℤqx/xn+1slFirstl bits of string sAMatricesℤqnn-dimensional vector of modulo q residue class ringℤqn×mn×m-dimensional matrix space of modulo q residue class ringℤmm-dimensional integer vector spacexVectors, assumed to be in column formRmm-dimensional real vector spacex⟵DChooses vectorx from probability distribution DxEuclidean norm of vectorxℝSet of real numbersneglnThe negligible function ofnBesides the symbols in Table1, this paper also uses symbols such as O˜,ω, which are commonly used symbols for computation complexity.


## 2.2. Related Definitions of NTRU Lattice

Definition 1 (convolutional polynomial ring).
Let ringR=ℤx/xn+1; when the addition operation on R remains unchanged and the multiplication operation can be replaced by a convolution operation, then R is called a convolution polynomial ring. Therefore, given a prime number q and a modular convolution polynomial ring Rq=R/qR.
Letf=∑i=0n−1fixi,g=∑i=0n−1gixi∈Rq; then, the two operations on Rq are defined as follows:(1)
Addition operation +:f+g=g=∑i=0n−1fi+giximodq∈Rq.(2)
Convolution operation∗: f∗g=f∗gmodxn+1∈Rq.Definition 2 (anti-circular matrices).
Let polynomialf∈Rq, and the coefficient vector of the polynomial f is f0,f1,…,fn−1; then, the coefficient vector of the polynomial x⋅f is −fn−1,f0,…,fn−2. By analogy, the coefficient vector of the polynomial xn−1⋅f is −f1,−f2,…,f0. That is, the anti-circular matrix Anf is composed of n polynomial vectors formed by successive cyclic shifts of the polynomial f∈Rq. So, the anti-circular matrix Anf can be expressed as a vector. The anti-circular matrix formed by polynomial f is as follows:(1)Anf=f0f1⋯fn−1−fn−1f0⋯fn−2⋮⋮⋯⋮−f1−f2⋯f0=fx∗f⋮xn−1∗f.Definition 3 (NTRU lattice).
n is a security parameter and is a power-of-two integer; let a prime q≥2 and polynomials f,g∈Rq,h=g∗f−1modq, satisfying f is reversible, where f−1∈Rq. Then, the NTRU lattice related to q and h is as follows:(2)Λq,h=u,v∈R2|u+v∗h=0modq.
NTRU latticeΛq,h is a 2n dimension full-rank lattice, Aq,h=−AnhInqIn0n∈ℤq2n×2n is a set of basis matrix of NTRU lattice, and it is uniquely defined by the polynomial h∈Rq. Therefore, the space required to store the basis matrix Aq,h is small. However, in the application of NTRU lattice-based cryptosystem, Aq,h cannot be used as a trapdoor basis because Aq,h has a very large orthogonal defect when the polynomial h∈Rq is uniformly distributed.Definition 4 (discrete Gaussian distribution).
For anyσ>0 and vector c∈Rm, the discrete Gaussian distribution centered on vector c over the lattice Λ is described as follows:(3)DΛ,σ,cx=ρσ,cxρσ,cΛ=ρσ,cx∑x∈Λρσ,cx,∀x∈Λ,where ρσ,cx=exp−πx−c2/σ2.
Whenc=0, the Gaussian distribution on Rm and the discrete distribution on lattice Λ can also be defined as Dσm and DΛ,σm, respectively.Lemma 1.
Given any parameterσ>0 and positive integer m, the following formulas hold [30]:(1)
Prx⟵Dσ1:x>ωσlogm=2−ωlogm.(2)
For any vectorx∈ℤm and σ≥log3m, there is Dσmx≤2−m+1.(3)
Prx⟵Dσm:x>2σm<2−m.


## 2.3. The NTRU-SIS Problems

Definition 5 (the SIS problem on NTRU lattice, NTRU-SIS).
Given parametersn,m,q, polynomial h=g∗f−1modq∈Rq, and a real number β>0, the NTRU-SIS problem is defined as follows: finding two non-zero small polynomials u,v∈Rq2 satisfying u+v∗h=0modq and u,v≤β.
NTRU-SIS Assumption. Given system linear equations of modulo q, without knowing the trapdoor, the advantage of finding two non-zero small polynomials u,v∈Rq2 that meet u+v∗h=0modq and u,v≤β can be neglected for any probabilistic polynomial time (PPT) algorithm.


## 2.4. Related Algorithms

Definition 6 (trapdoor generation algorithm on NTRU lattice).
Given integersn and k, where k>0 and n=2k, and a prime q=1mod2n, let a parameter s=1.17q/2n and f,g,F,G∈R satisfying f⋅F−g⋅G=q. The PPT algorithm TrapGenNTRUq,n,s [31] can output a polynomial h=g∗f−1modq and a set of short basis Bf,g=AngAnG−Anf−AnF∈ℤq2n×2n on NTRU lattice Λh,q.Definition 7 (discrete Gaussian sampling function).
In 2015, Lyubasevsky and Prest [32] proposed the compact Gaussian sampler (CGS) algorithm that can quickly implement discrete Gaussian distribution sampling on NTRU lattice.Theorem 1.
This is a more efficient polynomial time algorithmCGSB,σ,c [32]: on inputting a lattice basis B=b1,b2,…,bn, Gaussian parameter σ, and center vector c∈ℤm, the algorithm CGSB,σ,c can output the sampling z on distribution DΛB,σ,c.Lemma 2.
Let a parameterσ≥B⋅1/π1/2ln2+2/ε, where ε<2−λ/4n,log2n<λ<qn/2, such that the statistical distance between the output of CGSB,σ,c and the distribution DΛB,σ,c is no more than 2−λ.Definition 8 (rejection sampling).
In 2012, Lyubasevsky [30] proposed the rejection sampling and, based on this technology, first designed the signature scheme without trapdoor on the lattice. This technology can be applied to the signature system, which obtains the signature with a definite probability and makes the distribution of the signature and private key separate from one another so that the signature private key can be effectively prevented from leaking. The conclusions are as follows.Lemma 3.
For anyv∈ℤm,σ=ωvlogm, we have PrDσmz/Dv,σmz=O1:z⟵Dσm=1−2−ωlogm.Theorem 2.
LetV=v∈ℤm:v<t,σ=ωtlogm,h:V⟶ℝ be a probability distribution; for any constant M=O1, the statistical distance of output distribution between Algorithm 1 and Algorithm 2 is less than 2−ωlogm/M.Algorithm 1.
v⟵h;z⟵Dv,σm: output z,v with the probability of minDσmz/MDv,σmz,1.Algorithm 2.
v⟵h;z⟵Dσm: output z,v with the probability of 1/M.
Furthermore, the output probability of Algorithm1 is at least 1−2−ωlogm/M.


## 3. Definition of Identity-Based LRS and Security Model

### 3.1. Definition of Identity-Based LRS

An identity-based LRS [14, 33] is composed of five PPT algorithms:(1)
Setup1λ,1N: it inputs a security parameter λ, the number of ring members N, and returns the public parameters PP, and system master private key MSK.(2)
KeyGenPP,IDi,MSK: it inputs public parameters PP, user identity IDi, and system master private key MSK and returns a pair of public\private key pki,ski.(3)
SignPP,R,m,ski: it inputs public parameters PP, ring user identity set R=ID1,ID2,…,IDN, a message m∈0,1∗, and signature private key ski of user IDi∈R and outputs the ring signature σRm of user IDi on a message m∈0,1∗, which contains the linkability tag I.(4)
VerifyPP,R,m,σRm: it inputs public parameters PP, ring user identity set R=ID1,ID2,…,IDN, a message m∈0,1∗, and a signature σRm; if σRm is valid, the verifier returns “valid”; otherwise, it outputs “invalid.”(5)
LinkσR1m1,σR2m2: it inputs two ring signatures σR1m1,σR2m2 and verifies I1=?I2. If equal, the verifier returns “link.” It indicates that σR1m1,σR2m2 are produced by identical signer; otherwise, it outputs “unlink.”


### 3.2. Security Model

An identity-based LRS scheme definition of security should meet linkability in addition to correctness, anonymity, and unforgeability of ordinary ring signatures. Correctness includes verification correctness and linking correctness (refer to Definition9 for details). Anonymity implies that the attacker is unable to confirm which specific member of the ring generated the signature, and our scheme has strong anonymity, that is, unconditional anonymity (refer to Definition 10 for details). Unforgeability means that the members outside of the ring cannot, instead of the real signer, sign without the signer’s private key (refer to Definition 11 for details). Linkability means that users with only one private key cannot give two signatures, which successfully pass the detection of the linking algorithm (refer to Definition 12 for details). This paper is based upon the security model proposed by Liu et al. [14], using a series of games between a challenger C and an adversary A to characterize the security definition of this scheme. The adversary A can call on the random oracle and the oracles RO,CO,SO under the ROM.(i)
Registration oracle:A chooses a random user’s identity IDi to query and C uses the KeyGenPP,IDi,MSK algorithm to return the corresponding public key pki.(ii)
Corruption oracle:A chooses a random user’s identity IDi to query and C uses the KeyGenPP,IDi,MSK algorithm to return the corresponding private key ski.(iii)
Signing oracle:A inputs ring user identity set R=ID1,ID2,…,IDN, a message m∈0,1∗, and user’s identity IDi∈R to query, and C gives a valid signature σRm through running SignPP,R,m,ski algorithm.Definition 9 (correctness).
The correctness of the LRS scheme contains verification correctness and linking correctness simultaneously.(1)
Verification correctness: requires signatureσRm generated by users honestly in accordance with the specification; the probability of algorithm VerifyPP,R,m,σRm outputting “invalid” is negligible.(2)
Linking correctness: requires two valid signaturesσR1m1 and σR2m2 produced with the identical private key for the same signer; the probability of algorithm LinkσR1m1,σR2m2 outputting “unlink” is negligible.
The formal definition of the correctness of the LRS is as follows:(4)Pr“Invalid”⟵VerifyPP,R,m,σRmMSK,PP⟵Setup1λ,1Nsk⟵KeyGenPP,ID,MSKσRm⟵SignPP,R,m,sk≤negln,Pr“Unlink”⟵LinkσR1m1,σR2m2MSK,PP⟵Setup1λ,1Nsk⟵KeyGenPP,ID,MSKσR1m1⟵SignPP,R1,m1,skσR2m2⟵SignPP,R2,m2,sk≤negln.


#### 3.2.1. Unconditional Anonymity

Even if A possesses unlimited computational resources (with unbounded computation power and time), it can compute the corresponding private key when a public key is given. It is not feasible to distinguish the signer’s identity with a probability larger than 1/2. The unconditional anonymity of the LRS scheme is defined by the following game between an adversaryA and a challenger C.(1)
Setup: on receiving a security parameterλ and the number of ring members N, C calls the Setup1λ,1N algorithm to get the public parameters PP and system master private key MSK and gives the public parameters PP to A.(2)
Query:A is allowed to make adaptive inquiries to above oracles.(3)
Challenge:A inputs ring user identity set R=ID1,ID2,…,IDN and a message m∗∈0,1∗ and chooses two user identities IDi0, IDi1∈R for signing queries; C randomly selects a number b∈0,1 and then obtains the signature σRm∗⟵SignPP,R,m,ski. This signature σRm∗ is given to A.(4)
Guess:A gives guess b∗∈0,1. The adversary A wins if the conditions described below are satisfied:(a)
b∗=b.(b)
IDi0, IDi1∈R cannot be input by CO and SO.The advantage ofA is denoted by(5)AdvAanon=Prb∗=b−12.Definition 10 (unconditional anonymity).
The LRS scheme is unconditionally anonymous if the advantageAdvAanon≤negln for any PPT adversary A.


#### 3.2.2. Unforgeability

The unforgeability of the LRS scheme is defined by the following game between an adversaryA and a challenger C.(1)
Setup: given a security parameterλ and the number of ring members N, C calls the Setup1λ,1N algorithm to get the public parameters PP and system master private key MSK and sends the public parameters PP to A.(2)
Query:A is allowed to make adaptive inquiries to above oracles.(3)
Forge:A gives C a tuple m∗,R∗,σR∗m∗. The adversary A wins if the conditions described below are satisfied:(a)
Verifym∗,R∗,σR∗m∗=“Valid.”(b)
All of the public keys inR∗ are inquiry outputs of RO.(c)
The identity of anyone inR∗ has not been input to CO.(d)
σR∗m∗ is not an inquiry output of SO.The advantage ofA is denoted by(6)AdvAforge=PrAwins the game.Definition 11 (unforgeability).
The LRS scheme is unforgeable if the advantageAdvAforge≤negln for any PPT adversary A.


#### 3.2.3. Linkability

The linkability of the LRS scheme is defined by the following game between an adversaryA and a challenger C.(1)
Setup: on receiving a security parameterλ and the number of ring members N, C calls the Setup1λ,1N algorithm to get the public parameters PP and system master private key MSK and gives the public parameters PP to A.(2)
Query:A is allowed to make adaptive inquiries to above oracles.(3)
Forge:A gives C two message-signature pairs m1∗,R1∗,σR1∗m1∗,m2∗,R2∗,σR2∗m2∗, and the two signatures σR1∗m1∗,σR2∗m2∗ contain corresponding two linkability tags I1,I2. The adversary A wins if the conditions described below are satisfied:(a)
Verifymi∗,Ri∗,σRi∗mi∗=“Valid” for i=1,2.(b)
LinkσR1∗m1∗,σR2∗m2∗=“Unlinked.”(c)
All of the public keys inRi∗,i∈1,2 are outputs of RO.(d)
A has inquiredCO less than two times (that is, A has one private key of usersat most).(e)
σR1∗m1∗,σR2∗m2∗ are not inquired outputs of SO.The advantage ofA is denoted by(7)AdvAlink=PrAwins the game.Definition 12 (linkability).
The LRS scheme is linkable if the advantageAdvAlink≤negln for any PPT adversary A.


## 3.1. Definition of Identity-Based LRS

An identity-based LRS [14, 33] is composed of five PPT algorithms:(1)
Setup1λ,1N: it inputs a security parameter λ, the number of ring members N, and returns the public parameters PP, and system master private key MSK.(2)
KeyGenPP,IDi,MSK: it inputs public parameters PP, user identity IDi, and system master private key MSK and returns a pair of public\private key pki,ski.(3)
SignPP,R,m,ski: it inputs public parameters PP, ring user identity set R=ID1,ID2,…,IDN, a message m∈0,1∗, and signature private key ski of user IDi∈R and outputs the ring signature σRm of user IDi on a message m∈0,1∗, which contains the linkability tag I.(4)
VerifyPP,R,m,σRm: it inputs public parameters PP, ring user identity set R=ID1,ID2,…,IDN, a message m∈0,1∗, and a signature σRm; if σRm is valid, the verifier returns “valid”; otherwise, it outputs “invalid.”(5)
LinkσR1m1,σR2m2: it inputs two ring signatures σR1m1,σR2m2 and verifies I1=?I2. If equal, the verifier returns “link.” It indicates that σR1m1,σR2m2 are produced by identical signer; otherwise, it outputs “unlink.”


## 3.2. Security Model

An identity-based LRS scheme definition of security should meet linkability in addition to correctness, anonymity, and unforgeability of ordinary ring signatures. Correctness includes verification correctness and linking correctness (refer to Definition9 for details). Anonymity implies that the attacker is unable to confirm which specific member of the ring generated the signature, and our scheme has strong anonymity, that is, unconditional anonymity (refer to Definition 10 for details). Unforgeability means that the members outside of the ring cannot, instead of the real signer, sign without the signer’s private key (refer to Definition 11 for details). Linkability means that users with only one private key cannot give two signatures, which successfully pass the detection of the linking algorithm (refer to Definition 12 for details). This paper is based upon the security model proposed by Liu et al. [14], using a series of games between a challenger C and an adversary A to characterize the security definition of this scheme. The adversary A can call on the random oracle and the oracles RO,CO,SO under the ROM.(i)
Registration oracle:A chooses a random user’s identity IDi to query and C uses the KeyGenPP,IDi,MSK algorithm to return the corresponding public key pki.(ii)
Corruption oracle:A chooses a random user’s identity IDi to query and C uses the KeyGenPP,IDi,MSK algorithm to return the corresponding private key ski.(iii)
Signing oracle:A inputs ring user identity set R=ID1,ID2,…,IDN, a message m∈0,1∗, and user’s identity IDi∈R to query, and C gives a valid signature σRm through running SignPP,R,m,ski algorithm.Definition 9 (correctness).
The correctness of the LRS scheme contains verification correctness and linking correctness simultaneously.(1)
Verification correctness: requires signatureσRm generated by users honestly in accordance with the specification; the probability of algorithm VerifyPP,R,m,σRm outputting “invalid” is negligible.(2)
Linking correctness: requires two valid signaturesσR1m1 and σR2m2 produced with the identical private key for the same signer; the probability of algorithm LinkσR1m1,σR2m2 outputting “unlink” is negligible.
The formal definition of the correctness of the LRS is as follows:(4)Pr“Invalid”⟵VerifyPP,R,m,σRmMSK,PP⟵Setup1λ,1Nsk⟵KeyGenPP,ID,MSKσRm⟵SignPP,R,m,sk≤negln,Pr“Unlink”⟵LinkσR1m1,σR2m2MSK,PP⟵Setup1λ,1Nsk⟵KeyGenPP,ID,MSKσR1m1⟵SignPP,R1,m1,skσR2m2⟵SignPP,R2,m2,sk≤negln.


### 3.2.1. Unconditional Anonymity

Even if A possesses unlimited computational resources (with unbounded computation power and time), it can compute the corresponding private key when a public key is given. It is not feasible to distinguish the signer’s identity with a probability larger than 1/2. The unconditional anonymity of the LRS scheme is defined by the following game between an adversaryA and a challenger C.(1)
Setup: on receiving a security parameterλ and the number of ring members N, C calls the Setup1λ,1N algorithm to get the public parameters PP and system master private key MSK and gives the public parameters PP to A.(2)
Query:A is allowed to make adaptive inquiries to above oracles.(3)
Challenge:A inputs ring user identity set R=ID1,ID2,…,IDN and a message m∗∈0,1∗ and chooses two user identities IDi0, IDi1∈R for signing queries; C randomly selects a number b∈0,1 and then obtains the signature σRm∗⟵SignPP,R,m,ski. This signature σRm∗ is given to A.(4)
Guess:A gives guess b∗∈0,1. The adversary A wins if the conditions described below are satisfied:(a)
b∗=b.(b)
IDi0, IDi1∈R cannot be input by CO and SO.The advantage ofA is denoted by(5)AdvAanon=Prb∗=b−12.Definition 10 (unconditional anonymity).
The LRS scheme is unconditionally anonymous if the advantageAdvAanon≤negln for any PPT adversary A.


### 3.2.2. Unforgeability

The unforgeability of the LRS scheme is defined by the following game between an adversaryA and a challenger C.(1)
Setup: given a security parameterλ and the number of ring members N, C calls the Setup1λ,1N algorithm to get the public parameters PP and system master private key MSK and sends the public parameters PP to A.(2)
Query:A is allowed to make adaptive inquiries to above oracles.(3)
Forge:A gives C a tuple m∗,R∗,σR∗m∗. The adversary A wins if the conditions described below are satisfied:(a)
Verifym∗,R∗,σR∗m∗=“Valid.”(b)
All of the public keys inR∗ are inquiry outputs of RO.(c)
The identity of anyone inR∗ has not been input to CO.(d)
σR∗m∗ is not an inquiry output of SO.The advantage ofA is denoted by(6)AdvAforge=PrAwins the game.Definition 11 (unforgeability).
The LRS scheme is unforgeable if the advantageAdvAforge≤negln for any PPT adversary A.


### 3.2.3. Linkability

The linkability of the LRS scheme is defined by the following game between an adversaryA and a challenger C.(1)
Setup: on receiving a security parameterλ and the number of ring members N, C calls the Setup1λ,1N algorithm to get the public parameters PP and system master private key MSK and gives the public parameters PP to A.(2)
Query:A is allowed to make adaptive inquiries to above oracles.(3)
Forge:A gives C two message-signature pairs m1∗,R1∗,σR1∗m1∗,m2∗,R2∗,σR2∗m2∗, and the two signatures σR1∗m1∗,σR2∗m2∗ contain corresponding two linkability tags I1,I2. The adversary A wins if the conditions described below are satisfied:(a)
Verifymi∗,Ri∗,σRi∗mi∗=“Valid” for i=1,2.(b)
LinkσR1∗m1∗,σR2∗m2∗=“Unlinked.”(c)
All of the public keys inRi∗,i∈1,2 are outputs of RO.(d)
A has inquiredCO less than two times (that is, A has one private key of usersat most).(e)
σR1∗m1∗,σR2∗m2∗ are not inquired outputs of SO.The advantage ofA is denoted by(7)AdvAlink=PrAwins the game.Definition 12 (linkability).
The LRS scheme is linkable if the advantageAdvAlink≤negln for any PPT adversary A.


## 3.2.1. Unconditional Anonymity

Even if A possesses unlimited computational resources (with unbounded computation power and time), it can compute the corresponding private key when a public key is given. It is not feasible to distinguish the signer’s identity with a probability larger than 1/2. The unconditional anonymity of the LRS scheme is defined by the following game between an adversaryA and a challenger C.(1)
Setup: on receiving a security parameterλ and the number of ring members N, C calls the Setup1λ,1N algorithm to get the public parameters PP and system master private key MSK and gives the public parameters PP to A.(2)
Query:A is allowed to make adaptive inquiries to above oracles.(3)
Challenge:A inputs ring user identity set R=ID1,ID2,…,IDN and a message m∗∈0,1∗ and chooses two user identities IDi0, IDi1∈R for signing queries; C randomly selects a number b∈0,1 and then obtains the signature σRm∗⟵SignPP,R,m,ski. This signature σRm∗ is given to A.(4)
Guess:A gives guess b∗∈0,1. The adversary A wins if the conditions described below are satisfied:(a)
b∗=b.(b)
IDi0, IDi1∈R cannot be input by CO and SO.The advantage ofA is denoted by(5)AdvAanon=Prb∗=b−12.Definition 10 (unconditional anonymity).
The LRS scheme is unconditionally anonymous if the advantageAdvAanon≤negln for any PPT adversary A.


## 3.2.2. Unforgeability

The unforgeability of the LRS scheme is defined by the following game between an adversaryA and a challenger C.(1)
Setup: given a security parameterλ and the number of ring members N, C calls the Setup1λ,1N algorithm to get the public parameters PP and system master private key MSK and sends the public parameters PP to A.(2)
Query:A is allowed to make adaptive inquiries to above oracles.(3)
Forge:A gives C a tuple m∗,R∗,σR∗m∗. The adversary A wins if the conditions described below are satisfied:(a)
Verifym∗,R∗,σR∗m∗=“Valid.”(b)
All of the public keys inR∗ are inquiry outputs of RO.(c)
The identity of anyone inR∗ has not been input to CO.(d)
σR∗m∗ is not an inquiry output of SO.The advantage ofA is denoted by(6)AdvAforge=PrAwins the game.Definition 11 (unforgeability).
The LRS scheme is unforgeable if the advantageAdvAforge≤negln for any PPT adversary A.


## 3.2.3. Linkability

The linkability of the LRS scheme is defined by the following game between an adversaryA and a challenger C.(1)
Setup: on receiving a security parameterλ and the number of ring members N, C calls the Setup1λ,1N algorithm to get the public parameters PP and system master private key MSK and gives the public parameters PP to A.(2)
Query:A is allowed to make adaptive inquiries to above oracles.(3)
Forge:A gives C two message-signature pairs m1∗,R1∗,σR1∗m1∗,m2∗,R2∗,σR2∗m2∗, and the two signatures σR1∗m1∗,σR2∗m2∗ contain corresponding two linkability tags I1,I2. The adversary A wins if the conditions described below are satisfied:(a)
Verifymi∗,Ri∗,σRi∗mi∗=“Valid” for i=1,2.(b)
LinkσR1∗m1∗,σR2∗m2∗=“Unlinked.”(c)
All of the public keys inRi∗,i∈1,2 are outputs of RO.(d)
A has inquiredCO less than two times (that is, A has one private key of usersat most).(e)
σR1∗m1∗,σR2∗m2∗ are not inquired outputs of SO.The advantage ofA is denoted by(7)AdvAlink=PrAwins the game.Definition 12 (linkability).
The LRS scheme is linkable if the advantageAdvAlink≤negln for any PPT adversary A.


## 4. Scheme Construction

To decrease the signature length and promote the computational efficiency of existing LRS schemes. We designed an identity-based LRS scheme over NTRU lattice by employing technologies of trapdoor generation algorithm [31] and rejection sampling [30]. The construction idea of this paper is to introduce identity-based cryptography into the efficient NTRU lattice-based ring signature. During the system setup process, the system’s master key uses the trapdoor generation [31] algorithm to obtain NTRU lattice. In the key generation period, the private key is produced based upon the compact Gaussian sampler (CGS) algorithm [32], which effectively improves the speed of user key extraction. In the signature generation phase, through using the rejection sampling [30] technique to generate signature with a certain probability, the distribution of signature and private key is independent of each other, and the computational efficiency of signature is further optimized and improved. The proposed identity-based LRS scheme is as follows:(1)
Setup1λ,1N: by inputting a security parameter λ and the number of ring members N, it sets integer k>0, where integer n=2k, and chooses a prime number q=1mod2n, a parameter s=1.17q/2n, and a Gaussian parameter σ=117/200π⋅q⋅logexp2+2/η, where η=2−λ+1/n. It sets polynomial ring Rq=ℤqx/xn+1, and KGC obtains the public parameters PP and the system master private key MSK according to the following steps.(a)
KGC usesTrapGenNTRUq,n,s algorithm to generate a uniform and randomized polynomial h∈Rq together with a short basis B∈ℤq2n×2n on lattice Λq,h.(b)
Selects two collision-resistance hash functionsH1:0,1∗⟶ℤqn,H2:0,1∗⟶0,1n.(c)
The system master private key of KGC isMSK=B, and master public key is MPK=h.(d)
Outputs the public parametersPP=h,H1,H2 and keeps the system master private key MSK=B secret.(2)
KeyGenPP,IDi,MSK: given the public parameters PP, user’s identity IDi, and system master private key MSK=B, KGC obtains a pair of public\private key pki,ski as follows.(a)
Calculates the public keypki is ti,1=H1IDi∈ℤqn.(b)
Uses CGS sampling algorithm to generates1,s2=ti,1,0−CGSB,σ,ti,1,0, then s1+s2∗h=ti,1.(c)
Randomly chooses polynomial vectorss1∗,s2∗⟵Dσn and returns user’s private key ski=s1,s2,s1∗,s2∗.(3)
SignPP,R,m,skk: receives the public parameters PP, ring user identity set R=ID1,ID2,…,IDN, a message m∈0,1∗, and private key skk=s1,s2,s1∗,s2∗ of user IDk∈R. The signing process is as follows:(a)
CalculatesI=tk,1+tk,2∈Rq as the linkability tag, where tk,2=s1∗+s2∗∗h∈Rq.(b)
Randomly chooses polynomial vectorsyi,1,yi,2⟵Dσn,i∈1,2,…,N, and the vectors corresponding to short polynomials in Rq.(c)
Setsv=H2∑i=1Nyi,1+yi,2∗h,R,m,I.(d)
Ifi≠k, it sets zi,1=yi,1,zi,2=yi,2; if i=k, it calculates zi=zi,1zi,2=s1+s1∗s2+s2∗∗v+yi,1yi,2.(e)
By probabilityDο˜2nσzi,1,zi,2/MDs1+s1∗v,s2+s2∗v,ο˜2nσzi,1,zi,2, it outputs σRm=zi,1,zi,21≤i≤N,v,I as the signature, where M=O1.(4)
VerifyPP,R,m,σRm: receives the public parameters PP, ring user identity set R=ID1,ID2,…,IDN, a message m∈0,1∗, and a ring signature σRm=zi,1,zi,21≤i≤N,v,I. For i∈1,2,…,N, calculates and verifies whether the following conditions hold:(a)
zi,1≤2σn,zi,2≤2σn.(b)
H2∑i=1Nzi,1+zi,2∗h−I∗v,R,m,I=v.If conditions (a) and (b) are satisfied, the verifier will return “Valid” and then accept the messagem∈0,1∗ signed by a member of the ring user identity set R=ID1,ID2,…,IDN; otherwise, it outputs “Invalid.”(5)
LinkσR1m1,σR2m2: on inputting two signatures σR1m1,σR2m2, the verifier does these steps:Inputs two signaturesσR1m1 and σR2m2 and verifies I1=?I2; if I1=I2, it outputs “Link”; otherwise, it outputs “Unlink.”


## 5. Security Analysis

Theorem 3 (correctness).
The proposed identity-based LRS scheme is correct.Proof.
The proof is given in Appendix A.Theorem 4 (unconditional anonymity).
The proposed identity-based LRS scheme is unconditionally anonymous.Proof.
The proof is given in Appendix B.Theorem 5 (unforgeability).
The proposed identity-based LRS scheme is unforgeable under the ROM, if the SIS problem on the NTRU is hard.Proof.
The proof is given in Appendix C.Theorem 6 (linkability).
The proposed identity-based LRS scheme is linkable under the ROM, if the proposed LRS scheme is unforgeable.Proof.
The proof is given in Appendix D.


## 6. Discussion

We now discuss how the initial parameters are selected and point at the future research direction.


### 6.1. Parameter Selection

The security of the proposed scheme is based on the NTRU-SIS problem, which is defined as follows: finding two non-zero small polynomialsu,v∈Rq2 satisfying u+v∗h=0modq and u,v≤β. This problem can be reduced to the γ-ideal-SVP problem. According to the literature [34, 35], the value of γ measures the hardness of γ-ideal-SVP problem. We use the root-Hermite factor (RHF) γ to analyze the security level of the scheme and set the relevant parameters. According to the literature [34], if a polynomial vector v is found in an n-dimensional lattice Λ and the vector is greater than the nth root of the determinant, then the relative RHF is(8)γ=vdetΛ1/n1/n.If the small-size polynomial vectorv is found in the NTRU lattice Λq,h, then the relative RHF is(9)γ=2.5n/πexp⋅detΛq,h1/2nv1/2n.According to the results of literature [35, 36], when the value of γ is approximately 1.007, finding the vector satisfying the condition is at least 80-bits hard. When the value of γ is less than 1.004, finding the vector satisfying the condition is at least 192-bits hard.The methods of attacking the proposed scheme are mainly attacks on the public keys of ring members and the signatures.In the proposed scheme, the public key of ring memberi is ti,1=H1IDi. The attack on ti,1 is to find two non-zero small-size polynomials s1,s2∈Rq2 in the NTRU lattice that satisfy s1+s2∗h=ti,1. According to Definition 6, s1,s2≤s2n. The value of γ is calculated by (9), and we have γ=n/1.3681/2n. When n=256, γ≈1.0068, attacking the public key of ring members is at least 80-bits hard, and when n=512, γ≈1.0027, attacking the public key of ring members is at least 192-bits hard.In the proposed scheme, the signature of ring memberi is σRm=zi,1,zi,21≤i≤N,v,I. The attack on the signature is to find vectors zi,1,zi,2 through the verification algorithm without the private key of the ring member i. Then, the value of γ is calculated by formula (8), and we have(10)γ=zi,1,zi,2detΛq,h1/2n1/2n.From Lemma3 and Theorem 2, zi,1,zi,2≤σ2n, and we have(11)γ=σ2nq1/2n.The Gaussian parameter is defined asσ=117/200π⋅q⋅logexp2+2/η, where η=2−λ+1/n. Through further calculation, the following results can be obtained.(12)γ=σ2nq1/2n≈0.18624n+8n22−λ1/2n≈1.0076,n=256,λ=80,1.0038,n=512,λ=192.Whenn=256, γ≈1.0076, attacking the signature of ring members is at least 80-bits hard, and when n=512, γ≈1.0038, attacking the signature of ring members is at least 192-bits hard. The main parameters of this scheme are defined in Table 2.Table 2
Parameter setting for our scheme.
ParameternkλSecurity levelRecommended choice25688080-bits5129192192-bits


### 6.2. Post-Quantum Security

It is generally believed that the proposed scheme constructed based on the hardness assumption over lattices may provide post-quantum security. On the other hand, the security proof of the proposed scheme is unlikely to carry over to the quantum random oracle model [37] (QROM). We use adaptive programming of the RO H1 and H2 in the security proof (Theorems 4–6). This proof technology is inherent to the construction to some extent.We learned that other construction schemes in the QROM, such as [38, 39], also use a form of RO programming (even if they are not adaptive). As far as we know, though it seems unlikely that the Fiat–Shamir can be proven in the QROM, there are no attacks on the protocols using these proof techniques which are derived from the use of the RO. If the security of the scheme is proved in the QROM, the construction process of the proposed scheme may be subverted. In the next step, we will consider constructing an identity-based LRS on the NTRU lattice under the QROM.


## 6.1. Parameter Selection

The security of the proposed scheme is based on the NTRU-SIS problem, which is defined as follows: finding two non-zero small polynomialsu,v∈Rq2 satisfying u+v∗h=0modq and u,v≤β. This problem can be reduced to the γ-ideal-SVP problem. According to the literature [34, 35], the value of γ measures the hardness of γ-ideal-SVP problem. We use the root-Hermite factor (RHF) γ to analyze the security level of the scheme and set the relevant parameters. According to the literature [34], if a polynomial vector v is found in an n-dimensional lattice Λ and the vector is greater than the nth root of the determinant, then the relative RHF is(8)γ=vdetΛ1/n1/n.If the small-size polynomial vectorv is found in the NTRU lattice Λq,h, then the relative RHF is(9)γ=2.5n/πexp⋅detΛq,h1/2nv1/2n.According to the results of literature [35, 36], when the value of γ is approximately 1.007, finding the vector satisfying the condition is at least 80-bits hard. When the value of γ is less than 1.004, finding the vector satisfying the condition is at least 192-bits hard.The methods of attacking the proposed scheme are mainly attacks on the public keys of ring members and the signatures.In the proposed scheme, the public key of ring memberi is ti,1=H1IDi. The attack on ti,1 is to find two non-zero small-size polynomials s1,s2∈Rq2 in the NTRU lattice that satisfy s1+s2∗h=ti,1. According to Definition 6, s1,s2≤s2n. The value of γ is calculated by (9), and we have γ=n/1.3681/2n. When n=256, γ≈1.0068, attacking the public key of ring members is at least 80-bits hard, and when n=512, γ≈1.0027, attacking the public key of ring members is at least 192-bits hard.In the proposed scheme, the signature of ring memberi is σRm=zi,1,zi,21≤i≤N,v,I. The attack on the signature is to find vectors zi,1,zi,2 through the verification algorithm without the private key of the ring member i. Then, the value of γ is calculated by formula (8), and we have(10)γ=zi,1,zi,2detΛq,h1/2n1/2n.From Lemma3 and Theorem 2, zi,1,zi,2≤σ2n, and we have(11)γ=σ2nq1/2n.The Gaussian parameter is defined asσ=117/200π⋅q⋅logexp2+2/η, where η=2−λ+1/n. Through further calculation, the following results can be obtained.(12)γ=σ2nq1/2n≈0.18624n+8n22−λ1/2n≈1.0076,n=256,λ=80,1.0038,n=512,λ=192.Whenn=256, γ≈1.0076, attacking the signature of ring members is at least 80-bits hard, and when n=512, γ≈1.0038, attacking the signature of ring members is at least 192-bits hard. The main parameters of this scheme are defined in Table 2.Table 2
Parameter setting for our scheme.
ParameternkλSecurity levelRecommended choice25688080-bits5129192192-bits


## 6.2. Post-Quantum Security

It is generally believed that the proposed scheme constructed based on the hardness assumption over lattices may provide post-quantum security. On the other hand, the security proof of the proposed scheme is unlikely to carry over to the quantum random oracle model [37] (QROM). We use adaptive programming of the RO H1 and H2 in the security proof (Theorems 4–6). This proof technology is inherent to the construction to some extent.We learned that other construction schemes in the QROM, such as [38, 39], also use a form of RO programming (even if they are not adaptive). As far as we know, though it seems unlikely that the Fiat–Shamir can be proven in the QROM, there are no attacks on the protocols using these proof techniques which are derived from the use of the RO. If the security of the scheme is proved in the QROM, the construction process of the proposed scheme may be subverted. In the next step, we will consider constructing an identity-based LRS on the NTRU lattice under the QROM.


## 7. Performance Analysis

In this section, we choose three similar schemes to carry out efficiency analysis and comparison with our scheme. They are, respectively, the identity-based LRS scheme based on the bilinear pairings constructed by Deng et al. [15], the logarithmic (linkable) ring signatures on lattice from isogeny and lattice assumptions given by Beullens et al. [28], and the practical lattice-based LRS based upon the chameleon hash plus (CH+) function designed by Lu et al. [29]. We will perform efficiency analysis of our scheme and the other three schemes [15, 28, 29] and mainly focus on two areas: time costs and storage overhead.The time cost comparison and difficult assumption of the four schemes are listed in Table3. Comparison terms in Table 3 include signature generation cost, signature verification cost, difficult assumption,and other comparisons. This paper mainly analyzes relatively time-consuming processes such as matrix-vector multiplication and polynomial-polynomial multiplication operation, the pairing operation, and exponentiation operation. The relatively less time-consuming operations such as hash operation, polynomial and matrix addition, and subtraction operation are ignored. In Tables 3 and 4, n represents a positive integer, q is a large prime number, N represents the number of ring members, and k and l are small integers, e.g., k=3,l=4. TSD,TRS, respectively, represent the time spent for the discrete Gaussian sampling algorithm and the algorithm rejection sampling run once, and generally, TSD>TRS. TBP represents the pairing operation, and TMG1,TEG2 represent the scalar multiplication operation in additive group G1 and the exponentiation operation in group G2, respectively. Besides, T1 and T2, respectively, defined the time cost running the polynomial-polynomial multiplication and matrix-vector multiplication operation n times, and generally, T2>T1.Table 3
Comparison of time costs and difficult assumption.
SchemeSignature costVerification costDifficult assumptionIdentity-basedPost-quantum[15]4TBP+N+1TMG13TBP+NTMG1+TEG2DBDHYesNo[28]lnTSD+5k×nT2logN2k×nT2logNMSIS, MLWENoYes[29]2nN+1TSD+2nN+1T12nNT1CH+NoYesOurs2nNTSD+nN+1T1+2nTRSnNT1NTRU-SISYesYesTable 4
Comparison of storage overhead.
SchemePublic key sizePrivate key sizeSignature size[15]2logq2logq4+Nlogq[28]k×lnlogqlnlogqk×lnlogq+nlogN[29]nlogq9nlogq3N+1nlogqOursnlogq4nlogq2N+1nlogqThe scheme [15] is designed based on DBDH problem, which cannot resist the attack from a quantum computer, while the other three schemes are designed on lattice which can resist quantum computer attack. So, we only list the efficiency of the scheme and no longer compare it with other three schemes. However, in Section 8, the experimental evaluation of scheme [15] will be carried out and compared with our scheme. With respect to signature generation, our scheme mainly uses 2N times of the Gaussian sampling algorithm, N+1 times of the polynomial-polynomial multiplication operations, and one-time rejection sampling algorithm. Therefore, the time cost of signature generation is 2nNTSD+nN+1T1+2nTRS. From Table 3, our scheme achieves higher efficiency in signature generation compared with the scheme of [29]. The signature generation time of scheme [28] has logarithmic relationship with the number of ring members N while our scheme has linear relationship with N. When N becomes larger, it is believed that the signature generation time of [28] is superior to that of our scheme. However, when N is small, which scheme has better signature generation efficiency depends on the concrete setting of relevant parameters, e.g., k,l,n,N. In terms of signature verification, our scheme mainly carries out N times of polynomial-polynomial multiplication operations. Therefore, the signature verification time cost of the proposed scheme is nNT1. Compared with the scheme of [29], the proposed scheme obviously has higher efficiency. The comparison of signature verification is similar to that of signature generation between the scheme of [28] and ours. Moreover, our scheme provides identity-based properties, which effectively avoids the problem of certificate management. However, neither scheme [28] nor scheme [29] has this property. When the number of ring members is large, the management and verification of certificates will take up a lot of system resources and the efficiency of signature and verification will be affected.The storage overhead comparison of the four schemes is shown in Table4; comparison terms include the size of public/private key and the signature size. On the size of public/private key, the public key is defined as a n-dimensional vector, and the private key matches the four small polynomials in the ring Rq in this paper. Therefore, the size of public key is nlogq, and the size of private key is 4nlogq. For scheme [15], the public key and private key are elements in group G1. Therefore, the public\private key size is 2logq. Regarding scheme [28], the public key is obtained by multiplying two random ring polynomials from Rql and Rqk, respectively, and the private key is defined as ring polynomials from Rql. Therefore, the public\private key size is k×lnlogq and lnlogq, respectively. In scheme [29], the public key is defined as a small polynomial in the ring Rq, and the private key matches the nine small polynomials in the ring Rq. Therefore, the size of public key is nlogq, and the size of private key is 9nlogq. According to the comprehensive analysis, scheme [15] has the smallest public and private key size, the public key length of the proposed scheme is much smaller than [28], and the private key of the proposed scheme is significantly smaller than that of [29]. Moreover, when l>4, the length of the private key of this scheme is also smaller than that of scheme [28]. For signature size, the signature generated in this article is σRm=zi,1,zi,21≤i≤N,v,I. The polynomial vectors zi,1,zi,2,I correspond to the small-size polynomials in the ring Rq. Therefore, the signature size of our scheme is 2N+1nlogq. After comparison, the signature length of this scheme is smaller than that of scheme [29]. Because the signature size of scheme [28] is logarithmic, when the number of ring members N is large, the signature length of the proposed scheme is larger than that of scheme [28] and needs to be further optimized. Although the signature size of the proposed scheme is longer than that of [15], our scheme is designed based on hardness assumption over lattice and can effectively resist quantum attacks, while the scheme of [15] cannot.


## 8. Implementation and Evaluation

The parameter setting in our scheme is given in Table5 such that the proposed scheme is secure, and we implemented the scheme under the operating environment indicated in Table 6. We ran the signature generation and signature verification algorithms 1000 times, respectively. The specific time comparison results of our scheme and the schemes of [15, 28, 29] at security level λ=80 in the case of different numbers of ring members are shown in Table 7 (let the length of q,p be 160 bits and 512 bits, respectively, in the scheme of [15], and let n=256,q=232,k=3,l=4 in the scheme of [28], respectively; scheme [29] has the same parameter settings as our scheme). According to Table 7, the signature generation and verification time costs of our scheme are shorter than those of [15, 29]. Compared with the scheme in [28], the proposed scheme has higher signature calculation efficiency when N≤512. When N≤256, the verification time cost of the proposed scheme is smaller than that of [28]. However, when the ring members N are large, the signature generation and verification efficiency of our scheme need to be improved compared with [28]. Finally, we use Table 8 to show the specific time costs of the signature generation and verification of our scheme under two different parameter types (I, II) when the number of ring members is different. After calculation, on average, the signature generation time cost of our scheme decreases roughly by 44.951%, and the signature verification time cost also decreases roughly by 33.503% compared with the other three schemes [15, 28, 29]. To show the advantage of our scheme in view of time costs more intuitively, we draw Figures 2 and 3. They, respectively, depict the signature generation and verification time costs of our scheme compared with other schemes under different numbers of ring members at security level λ=80. In summary, our scheme achieves relatively higher computational efficiency.Table 5
Parameter setting for our scheme.
ParameterTypenkqSecurity levelRecommended choiceI256823280-bitsII5129233192-bitsTable 6
Experimental environment configuration description.
EquipmentVersionOperating systemWindows10CPUIntel(R)Core(TM)i5-8300HCPUMemory8.00 GBWord size64 bitsCPU clock speed2.30 GHzTable 7
Comparison of time costs (ms) at security levelλ=80.
SchemeSignature timeN = 1N = 8N = 64N = 128N = 256N = 512N = 1024N = 2048[15]32.0840.77110.26189.69348.53666.231301.622572.40[28]33.7699.41198.86231.01265.16298.31331.46363.61[29]3.6213.5278.56149.52286.27510.87986.842001.91Ours2.147.2239.9175.26144.38261.02511.741012.70SchemeVerification timeN = 1N = 8N = 64N = 128N = 256N = 512N = 1024N = 2048[15]23.4232.13101.63181.05339.90657.601292.992563.77[28]13.2039.6579.2292.41105.60118.83135.68152.46[29]1.236.6449.9294.72162.75316.16622.561172.64Ours0.744.6826.5649.9294.72162.72316.16622.56Table 8
Time costs of our scheme (ms).
ParameterSignature timeN = 1N = 8N = 64N = 128N = 256N = 512N = 1024N = 2048I2.147.2239.9175.26144.38261.02511.741012.70II2.448.6346.4687.26164.54321.82618.301168.86ParameterVerification timeN = 1N = 8N = 64N = 128N = 256N = 512N = 1024N = 2048I0.744.6826.5649.9294.72162.72316.16622.56II0.845.5229.9255.36101.92197.76371.36676.16Figure 2
Comparison of time costs at security levelλ=80. The time cost of signature generation of schemes [15,28,29] is compared with our scheme in the case of different numbers of ring members.Figure 3
Comparison of time costs at security levelλ=80. The time cost of signature verification of schemes [15, 28, 29] is compared with our scheme in the case of different numbers of ring members.The size of public/private key and signature of the schemes of [15, 27, 28] and our scheme at security level λ=80 under different numbers of ring members are listed in Table 9. On the size of public key, the public key size of our scheme is equal to that of scheme [29] but is significantly smaller than that of scheme [28]. In terms of private key size, the scheme in [29] has the biggest private key, and the scheme of [15] has the smallest private key. However, the scheme of [15] is designed based on classical number theory problem (DBDH) and cannot resist quantum attacks. Compared with other lattice-based schemes, the proposed scheme has obvious advantages in key storage overhead. In view of signature size, the signature length of our scheme is short and is significantly better than that of [29]. When N≥64, the signature length of scheme [28] is shorter than that of our scheme, but note that scheme of [28] is not identity-based, which has the problem of certificate management. After further calculation, the size of signature decreases roughly by 32.078% compared with the scheme of [29] on average. Finally, we give the signature size of the proposed scheme under different parameter types (I, II) and different number of ring members in Table 10.Table 9
Comparison of storage overhead (kB) at security levelλ=80.
Scheme[15][28][29]OursSize of public key0.6131.562.632.63Size of private key0.6110.5223.6710.52Signature size forN = 13.0534.1910.526.89Signature size forN = 87.3239.4565.7538.71Signature size forN = 6441.4847.34507.59339.27Signature size forN = 12880.5249.971012.55675.91Signature size forN = 256158.6052.602022.471349.19Signature size forN = 512314.7655.234042.312695.75Table 10
Signature size of our scheme under different parameter settings (kB).
ParameterIIISignature size forN = 16.8915.69Signature size forN = 838.7188.91Signature size forN = 64339.27674.67Signature size forN = 128675.911344.11Signature size forN = 2561349.192682.99Signature size forN = 5122695.755360.75


## 9. Conclusions

Linkable ring signature performs a very important role in cryptography. Compared with ordinary ring signatures, it could not only protect the user’s identity privacy but also detect whether a user has completed two or more signatures with the same private key by running the linking algorithm. Moreover, lattice-based linkable ring signature can resist the attacks of quantum algorithms. When applied to the blockchain, besides protecting the privacy of both parties in the transaction, it can effectively prevent the emergence of “double-spending” problems. This paper based on the NTRU-SIS assumption constructed an identity-based LRS scheme over NTRU lattice [40]. Performance analysis and experiments show that this scheme has a smaller size of key and signature, thus reducing storage overhead. Since the NTRU lattice is a public key cryptosystem on account of the polynomial ring, the calculation process only involves multiplication in the polynomial ring and modular operations of small integers, which further improves the productivity of signature generation and signature verification of this scheme. This scheme has higher computation performance and lower communication and storage overhead, and it can be applied to more application scenarios than ordinary ring signature.



---

*Source: 9992414-2021-09-16.xml*