# Efficient Linkable Ring Signature Scheme over NTRU Lattice with Unconditional Anonymity

Authors: Qing Ye; Mengyao Wang; Hui Meng; Feifei Xia; Xixi Yan
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

In cloud and edge computing, senders of data often want to be anonymous, while recipients of data always expect that the data come from a reliable sender and they are not redundant. Linkable ring signature (LRS) can not only protect the anonymity of the signer, but also detect whether two different signatures are signed by the same signer. Today, most lattice-based LRS schemes only satisfy computational anonymity. To the best of our knowledge, only the lattice-based LRS scheme proposed by Torres et al. can achieve unconditional anonymity. But the efficiency of signature generation and verification of the scheme is very low, and the signature length is also relatively long. With the preimage sampling, trapdoor generation, and rejection sampling algorithms, this study proposed an efficient LRS scheme with unconditional anonymity based on the e-NTRU problem under the random oracle model. We implemented our scheme and Torres et al.’s scheme, as well as other four efficient lattice-based LRS schemes. It is shown that under the same security level, compared with Torres et al.’s scheme, the signature generation time, signature verification time, and signature size of our scheme are reduced by about 94.52%, 97.18%, and 58.03%, respectively.


---

## Body

## 1. Introduction

In most scenarios involving data transmission, including blockchain, cloud computing, edge computing, etc., the sender of data usually wants to be anonymous, while the receiver of data always excepts the data to be reliable. Ring signature (RS) proposed by Rivest et al. [1] is a good technology that can meet the above requirements. RS has two essential security properties: (1) unforgeability, which requires the verifier is able to verify whether the signature was signed by a reliable signer; and (2) anonymity, which requires the verifier could not identify the real signer from a group of users. Similar to group signature [2, 3], RS is group-oriented. However, different from group signature, in RS, the group is formed spontaneously, that is, there is no special manager, and the setup and revocation procedures are not required. Any user can select a group of ring members and sign any message with his own private key and the public keys of other members without their consent. And the verifier only can verify whether the signature comes from a member in the ring without knowing which member the signer is.Due to the anonymity of RS, it is widely used in anonymous tip off, e-cash [4], and other fields. It is worth noting that while protecting the anonymity of signers, RS also brings a new problem, that is, the same signer can sign multiple times without being detected.In 2004, Liu et al. [5] introduced an extended property called linkability to RS, and the corresponding primitive is now known as linkable ring signatures (LRS). LRS not only satisfies the properties of ordinary RS (such as correctness, unforgeability, and anonymity) but also can be used to judge whether two different signatures are signed by the same signer (linkability). LRS is useful in situations where anonymity and nonrepeatability are required. For example, in the system of blockchain [6], if some user signs the same amount of money twice, LRS will help the verifier detect it and the verifier will deny the second signature, thus avoiding the so-called “double spending” problem. In smart grid systems [7], the electricity consumption data of users are automatically collected by the smart meter, and specific electricity consumption information is fed back to the service provider. Thus, malicious attackers can infer the life and rest rules of the user from the large amount of electricity consumption data recorded by the smart meter. LRS can not only conceal the specific information of the meter user but also eliminate the redundant data of the same meter and provide the system with abnormal user monitoring and tracking functions.In 2013, Liu et al. [8] constructed an unconditional anonymous linkable ring signature (UALRS) scheme, which addressed the open problem that RS could not have linkability and strong anonymity simultaneously and made it more secure. RS schemes have two types of anonymity: computational anonymity and unconditional anonymity. Computational anonymity refers to the protection of anonymity under certain number theory problems. The anonymity of RS is destroyed if this potential problem can be solved by an adversary. By contrast, unconditional anonymity means that the probability that any adversary with unlimited computing power and time knows the actual signer of a given RS is no better than random guessing. In other words, assuming that there are l users in RS, the probability of any adversary with unlimited computing power and time correctly indicating the public key of the actual signer is no more than 1/l.It is not difficult to design a RS scheme with unconditional anonymity. In fact, most traditional RS schemes can satisfy unconditional anonymity [1, 9–16]. However, it is not an easy work to construct a UALRS scheme. The difficulty lies in the following two aspects. First, in a computational anonymous linkable ring signature (CALRS) scheme, the linking tag can always be designed as a pseudorandom function about the private key of the signer based on some mathematical problem. But unconditional anonymity means that the adversary has unlimited computing power, that is it can calculate out the solution of any NP-hard problem, such as NTRU-SIS, large integer factorization, discrete logarithm, and the preimage of a given hash value. Therefore, only designing the linking tag using mathematical problems is not enough, and it should consider more skills. Second, in order to achieve unconditional anonymity, the generation and verification of a linking tag are often more complex, which may increase the length of public and private keys and signatures, as well as reduce the computational efficiency of the scheme. In fact, from 2004 to 2013, only the LRS scheme proposed by Liu et al. [8] can achieve unconditional anonymity.The above schemes are all constructed based on classical number theory problems, that is, discrete logarithm and the decomposition of large integer problems. With the development of quantum computers, cryptosystems under classical number theory problems are faced with severe challenges. Shor [17] constructed a quantum algorithm in 1994 to solve the problem of large integer factorization in polynomial time under quantum computing conditions, and this algorithm made most existing public key cryptosystems no longer secure under quantum attacks.In this case, post-quantum cryptography began to be studied by scholars in the field of cryptography. In the alternatives, lattice-based cryptography appeals to scholars because of its high efficiency, simplicity, high parallelizability, and strong provable security guarantees. In 2016, Libert et al. [18] constructed a lattice-based RS scheme based on zero-knowledge proofs and accumulators. Thereafter, other lattice-based RS schemes have been proposed [19–21]. In 2017, Yang et al. [22] proposed a lattice-based LRS scheme based on week pseudorandom functions, accumulators, and zero-knowledge proofs. In 2018, Baum et al. [23] proposed the lattice-based one-time LRS scheme based on the module-SIS problem (a variant of SIS problem) and module-LWE problem (a variant of LWE problem). In the same year, Alberto Torres et al. [24] proposed a lattice-based one-time LRS scheme based on the ring-SIS problem. Subsequently, Zhang et al. [25] proposed a LRS scheme over ideal lattice based on the homomorphic commitment scheme and ∑ protocol. In 2019, Liu et al. [26] proposed a lattice-based LRS scheme supporting stealth addresses under the module-SIS and module-LWE problems. In 2020, Beullens et al. [27] constructed a LRS scheme whose signature size scales logarithmically with the ring size from isogeny and lattice assumptions.However, in the above lattice-based LRS schemes, only Alberto Torres et al.’s scheme [24] satisfies unconditional anonymity. By analyzing Torres et al.’s scheme, it is found that in order to achieve unconditional anonymity, the linking tag of Torres et al.’s scheme is generated using an m-dimensional polynomial vector over a polynomial ring. Since the linking tag is so large, Torres et al.’s scheme generates signatures m times longer than a normal CALRS scheme over a polynomial ring, and its efficiency in generating and verifying signatures is also significantly reduced.Hoffstein et al. [28] proposed the NTRU lattice-based cryptosystem in 1996. Considering that it only involves multiplication on polynomial rings and small integer modulo operations, the NTRU-based cryptosystem usually requires smaller public and private keys and is more efficient compared with that on the general lattice. Therefore, it has received extensive attention from scholars. In 2016, Zhang et al. [29] proposed an efficient RS scheme on NTRU lattice whose security can be reduced to the e-NTRU problem (a variant of the SIS problem on NTRU lattice) in the random oracle model. In 2019, Lu et al. [30] constructed Raptor, a practical NTRU lattice-based LRS scheme based on a variant of chameleon hash functions. In 2021, Tang et al. [31] constructed an identity-based 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.


### 1.1. Our Contribution

To reduce the signature size, as well as promote the efficiency of signature generation and verification of lattice-based UALRS scheme [24], in this study, a LRS scheme is reconstructed on NTRU lattice, and its architecture is shown in Figure 1. The main contributions of this article are as follows:(1)
In the key generation stage, the public and private keys of the LRS scheme are generated by the trapdoor and the preimage sampling algorithms on NTRU lattice. Then, the linking tag is produced by the public and private keys of the signer, and a LRS is generated based on the signature algorithm of Zhang et al. [29] combined with the rejection sampling algorithm.(2)
In terms of security analysis, strict security proof is conducted based on the security model of UALRS proposed by Liu et al. [8]. The result of the proof shows that the unforgeability and linkability of the proposed scheme can be reduced to the difficulty of e-NTRU problem under the random oracle model, and, meanwhile, the proposed scheme satisfies unconditional anonymity.(3)
In terms of performance analysis, the proposed scheme is compared with the latest and efficient lattice-based LRS schemes in [23, 24, 26, 27, 30], and a detailed analysis is given. The possible parameter settings of the proposed scheme are also analyzed and provided under the premise of ensuring the security of the proposed scheme.(4)
We implement our scheme and Torres et al.’s scheme [24], as well as other four efficient lattice-based LRS schemes [23, 26, 27, 30], and it is shown that under the same security level, the signature generation and verification time of the proposed scheme are respectively reduced by 56.61% and 65.18%. Especially compared with Torres et al.’s scheme, the signature generation and verification time of the proposed scheme are respectively reduced by 94.52% and 97.18%, and the signature size of the proposed scheme is reduced by 58.03% on average.Figure 1
Linkable ring signature on NTRU lattice.


### 1.2. Paper Organization

In Section2, we introduce some definitions, lemmas, difficult problems, and related algorithms which we will use to construct the scheme. We introduce the definition of LRS and the relevant security model in Section 3. Section 4 contains the construction and correctness statement of the LRS scheme and the proof of correctness. Section 5 contains the security statements of the proposed scheme and the proofs of unforgeability, unconditional anonymity, and linkability. In Section 6, we discuss the parameter settings and post-quantum security of the proposed scheme. Finally, in Section 7 and Section 8, we respectively give the performance analysis and experimental results of the proposed scheme and the lattice-based LRS schemes of [23, 24, 26, 27, 30] and also make a comparison between them.


## 1.1. Our Contribution

To reduce the signature size, as well as promote the efficiency of signature generation and verification of lattice-based UALRS scheme [24], in this study, a LRS scheme is reconstructed on NTRU lattice, and its architecture is shown in Figure 1. The main contributions of this article are as follows:(1)
In the key generation stage, the public and private keys of the LRS scheme are generated by the trapdoor and the preimage sampling algorithms on NTRU lattice. Then, the linking tag is produced by the public and private keys of the signer, and a LRS is generated based on the signature algorithm of Zhang et al. [29] combined with the rejection sampling algorithm.(2)
In terms of security analysis, strict security proof is conducted based on the security model of UALRS proposed by Liu et al. [8]. The result of the proof shows that the unforgeability and linkability of the proposed scheme can be reduced to the difficulty of e-NTRU problem under the random oracle model, and, meanwhile, the proposed scheme satisfies unconditional anonymity.(3)
In terms of performance analysis, the proposed scheme is compared with the latest and efficient lattice-based LRS schemes in [23, 24, 26, 27, 30], and a detailed analysis is given. The possible parameter settings of the proposed scheme are also analyzed and provided under the premise of ensuring the security of the proposed scheme.(4)
We implement our scheme and Torres et al.’s scheme [24], as well as other four efficient lattice-based LRS schemes [23, 26, 27, 30], and it is shown that under the same security level, the signature generation and verification time of the proposed scheme are respectively reduced by 56.61% and 65.18%. Especially compared with Torres et al.’s scheme, the signature generation and verification time of the proposed scheme are respectively reduced by 94.52% and 97.18%, and the signature size of the proposed scheme is reduced by 58.03% on average.Figure 1
Linkable ring signature on NTRU lattice.


## 1.2. Paper Organization

In Section2, we introduce some definitions, lemmas, difficult problems, and related algorithms which we will use to construct the scheme. We introduce the definition of LRS and the relevant security model in Section 3. Section 4 contains the construction and correctness statement of the LRS scheme and the proof of correctness. Section 5 contains the security statements of the proposed scheme and the proofs of unforgeability, unconditional anonymity, and linkability. In Section 6, we discuss the parameter settings and post-quantum security of the proposed scheme. Finally, in Section 7 and Section 8, we respectively give the performance analysis and experimental results of the proposed scheme and the lattice-based LRS schemes of [23, 24, 26, 27, 30] and also make a comparison between them.


## 2. Preliminaries

### 2.1. Symbol Definition

Descriptions of the used notations are listed in Table1.Table 1
Symbol description.
NotationsExplanationℝSet of real numbersℤSet of integersℤqSet of integers moduloqℤmSet ofm-dimensional column vectors over ℤℤqn×mSet of matrices ofn rows and m columns over ℤqRPolynomial ringℤx/xn+1RqPolynomial ringℤqx/xn+1AMatrixxVectorx←DRandomly choosing vectorx from probability distribution DxEuclidean norm of vectorxf⋅gMultiplication of polynomialsneglnNegligible function aboutngn=ωfngn>fn


### 2.2. Related Definitions of NTRU Lattice

Definition 1 (lattice).
LatticeΛ generated by m linearly independent vectors b1,b2,⋯,bm∈ℝn is the set of linear combinations of all integer coefficients of the m linearly independent vectors, namely(1)Λ=Lb1,b2,⋯,bm=∑i=1maibi|ai∈ℤ,where m and n are the rank and dimension of lattice Λ, respectively, and b1,b2,⋯,bm is called a basis of lattice Λ.Definition 2 (convolutional polynomial ring).
LetR=ℤx/xn+1 be an ordinary polynomial ring. If the addition operation remains unchanged and the multiplication operation is replaced by a convolution operation on R, then R is called a convolution polynomial ring. Similarly, given a prime number q, the modulus convolution polynomial ring is Rq=R/qR.
Letf=∑i=0n−1fixi,g=∑i=0n−1gixi∈Rq, then the two operations on Rq are defined as follows:(i)
Addition operation+:(2)f+g=∑i=0n−1fi+giximodq∈Rq.(ii)
Convolution operation∗:(3)f∗g=f⋅gmodxn+1modq∈Rq.Definition 3 (anticirculant matrix).
Let the coefficient vector of polynomialf be f0,f1,⋯,fn−1. Then, the coefficient vector of polynomial x⋅f is −fn−1,f0,⋯,fn−2 and the coefficient vector of polynomial xn−1⋅f is −f1,−f2,⋯,f0. The anti-circulant matrix defined by polynomial f is as follows:(4)Anf=f0−fn−1⋮−f1f1⋯fn−1f0⋯fn−2⋮⋯⋮−f2⋯f0=fx⋅f⋮xn−1⋅f.Definition 4.
(NTRU lattice). Let a positive integerq≥2, n is a power of two and f,g∈Rq, f−1∈Rq be the inverse of f, h=g∗f−1modq. The NTRU lattice corresponding to q and h is as follows:(5)Λq,h=u,v∈R2|u+v∗h=0modq.
Apparently, latticeΛq,h is a 2n-dimensional full-rank lattice, and Aq,h=−AnhInqInOn∈ℤq2n×2n is a set of basis matrices. Aq,h can be uniquely determined by the polynomial h∈Rq, whereas the others can be compressed during storage. Thus, the storage space required is relatively small. However, in NTRU lattice-based cryptographic schemes, Aq,h cannot be used as a trapdoor basis because it has poor orthogonality.Definition 5.
(discrete gaussian distribution) [32]. For any σ>0 and m-dimensional integer lattice Λ, the discrete Gaussian distribution on integer lattice Λ with vector c∈ℝm as the center and σ as the parameter is defined as follows:(6)∀x∈Λ,DΛ,c,σmx=ρc,σmxρc,σmΛ,where ρc,σmx=exp−πx−c2/σ2. When c=0, let ρc,σm and DΛ,c,σm be abbreviated as ρσm and DΛ,σm, respectively. And throughout the article, Dc,σm denotes the discrete Gaussian distribution over ℤm.


### 2.3. Hardness Assumption

Definition 6 (NTRU small-integer solution, NTRU-SIS) [33].
For a polynomialh=g∗f−1modq∈Rq and a real number β>0, to find two nonzero polynomials u,v∈Rq2 such that u+v∗h=0modq and u,v≤β.Definition 7 (extended NTRU, e-NTRU) [29].
GivenN polynomials hi=gi∗fi−1modq∈Rq,i∈1,⋯,N, where N≪q, to find a tuple of short polynomials ui,vi∈Rq2, ui,vi≠0modq,i∈1,⋯,N such that(7)∑i=1Nui+vi∗hi=0modq,ui,vi≤β,i∈1,⋯,N.Theorem 1 (see [29]).
Let integerk>0,n=2k,q=1mod2n and integer N≪q, then the e-NTRU problem is polynomially equivalent to the NTRU-SIS problem.


### 2.4. Related Algorithm

Lemma 1 (see [34]).
Let an integern=2k for k>0, a prime number q=1mod2n, and a parameter σ=1.17q/2n. Then, a probabilistic polynomial time (PPT) algorithm TrapGenn,q,σ can output a sample matrix Bf,g∈ℤq2n×2n from (a distribution close to) Dh,σ2n×2n and a polynomial h=g∗f−1modq∈Rq on the NTRU lattice Λh,q.Lemma 2 (see [34]).
Given a matrixBf,g and a parameter s=0.585/πqln2+2/η for η=2−λ/2n, where λ is the security parameter. For any polynomial t∈Rq, a PPT algorithm SamplePreBf,g,s,t may output z=z1,z2←Dh⊥+c,s, such that z1+z2∗h=t,z≤s2n.Definition 8 (rejection sampling algorithm) [35].
In 2012, Lyubashevsky proposed rejection sampling technique for the first time and gave the first signature scheme without trapdoor on lattice with this technique. It can be applied to the signature system and can make the distributions of the signature and private key independent of each other. Thus, it can effectively prevent the leakage of the private key.Lemma 3.
LetV=v∈ℤm:v<t, σ=ωtlogm, and h:V⟶ℝ is a probability distribution. Then, for constant M=O1, the statistical distance of output distributions of Algorithms 1 and 2 is less than 2−ωlogm/M.Algorithm 1.
v←h, z←Dv,σm, output z,v with probability minDσmz/MDv,σmz,1.Algorithm 2.
v←h, z←Dσm, output z,v with probability 1/M.
Furthermore, the output probability of Algorithm 1 is at least1−2−ωlogm/M.


## 2.1. Symbol Definition

Descriptions of the used notations are listed in Table1.Table 1
Symbol description.
NotationsExplanationℝSet of real numbersℤSet of integersℤqSet of integers moduloqℤmSet ofm-dimensional column vectors over ℤℤqn×mSet of matrices ofn rows and m columns over ℤqRPolynomial ringℤx/xn+1RqPolynomial ringℤqx/xn+1AMatrixxVectorx←DRandomly choosing vectorx from probability distribution DxEuclidean norm of vectorxf⋅gMultiplication of polynomialsneglnNegligible function aboutngn=ωfngn>fn


## 2.2. Related Definitions of NTRU Lattice

Definition 1 (lattice).
LatticeΛ generated by m linearly independent vectors b1,b2,⋯,bm∈ℝn is the set of linear combinations of all integer coefficients of the m linearly independent vectors, namely(1)Λ=Lb1,b2,⋯,bm=∑i=1maibi|ai∈ℤ,where m and n are the rank and dimension of lattice Λ, respectively, and b1,b2,⋯,bm is called a basis of lattice Λ.Definition 2 (convolutional polynomial ring).
LetR=ℤx/xn+1 be an ordinary polynomial ring. If the addition operation remains unchanged and the multiplication operation is replaced by a convolution operation on R, then R is called a convolution polynomial ring. Similarly, given a prime number q, the modulus convolution polynomial ring is Rq=R/qR.
Letf=∑i=0n−1fixi,g=∑i=0n−1gixi∈Rq, then the two operations on Rq are defined as follows:(i)
Addition operation+:(2)f+g=∑i=0n−1fi+giximodq∈Rq.(ii)
Convolution operation∗:(3)f∗g=f⋅gmodxn+1modq∈Rq.Definition 3 (anticirculant matrix).
Let the coefficient vector of polynomialf be f0,f1,⋯,fn−1. Then, the coefficient vector of polynomial x⋅f is −fn−1,f0,⋯,fn−2 and the coefficient vector of polynomial xn−1⋅f is −f1,−f2,⋯,f0. The anti-circulant matrix defined by polynomial f is as follows:(4)Anf=f0−fn−1⋮−f1f1⋯fn−1f0⋯fn−2⋮⋯⋮−f2⋯f0=fx⋅f⋮xn−1⋅f.Definition 4.
(NTRU lattice). Let a positive integerq≥2, n is a power of two and f,g∈Rq, f−1∈Rq be the inverse of f, h=g∗f−1modq. The NTRU lattice corresponding to q and h is as follows:(5)Λq,h=u,v∈R2|u+v∗h=0modq.
Apparently, latticeΛq,h is a 2n-dimensional full-rank lattice, and Aq,h=−AnhInqInOn∈ℤq2n×2n is a set of basis matrices. Aq,h can be uniquely determined by the polynomial h∈Rq, whereas the others can be compressed during storage. Thus, the storage space required is relatively small. However, in NTRU lattice-based cryptographic schemes, Aq,h cannot be used as a trapdoor basis because it has poor orthogonality.Definition 5.
(discrete gaussian distribution) [32]. For any σ>0 and m-dimensional integer lattice Λ, the discrete Gaussian distribution on integer lattice Λ with vector c∈ℝm as the center and σ as the parameter is defined as follows:(6)∀x∈Λ,DΛ,c,σmx=ρc,σmxρc,σmΛ,where ρc,σmx=exp−πx−c2/σ2. When c=0, let ρc,σm and DΛ,c,σm be abbreviated as ρσm and DΛ,σm, respectively. And throughout the article, Dc,σm denotes the discrete Gaussian distribution over ℤm.


## 2.3. Hardness Assumption

Definition 6 (NTRU small-integer solution, NTRU-SIS) [33].
For a polynomialh=g∗f−1modq∈Rq and a real number β>0, to find two nonzero polynomials u,v∈Rq2 such that u+v∗h=0modq and u,v≤β.Definition 7 (extended NTRU, e-NTRU) [29].
GivenN polynomials hi=gi∗fi−1modq∈Rq,i∈1,⋯,N, where N≪q, to find a tuple of short polynomials ui,vi∈Rq2, ui,vi≠0modq,i∈1,⋯,N such that(7)∑i=1Nui+vi∗hi=0modq,ui,vi≤β,i∈1,⋯,N.Theorem 1 (see [29]).
Let integerk>0,n=2k,q=1mod2n and integer N≪q, then the e-NTRU problem is polynomially equivalent to the NTRU-SIS problem.


## 2.4. Related Algorithm

Lemma 1 (see [34]).
Let an integern=2k for k>0, a prime number q=1mod2n, and a parameter σ=1.17q/2n. Then, a probabilistic polynomial time (PPT) algorithm TrapGenn,q,σ can output a sample matrix Bf,g∈ℤq2n×2n from (a distribution close to) Dh,σ2n×2n and a polynomial h=g∗f−1modq∈Rq on the NTRU lattice Λh,q.Lemma 2 (see [34]).
Given a matrixBf,g and a parameter s=0.585/πqln2+2/η for η=2−λ/2n, where λ is the security parameter. For any polynomial t∈Rq, a PPT algorithm SamplePreBf,g,s,t may output z=z1,z2←Dh⊥+c,s, such that z1+z2∗h=t,z≤s2n.Definition 8 (rejection sampling algorithm) [35].
In 2012, Lyubashevsky proposed rejection sampling technique for the first time and gave the first signature scheme without trapdoor on lattice with this technique. It can be applied to the signature system and can make the distributions of the signature and private key independent of each other. Thus, it can effectively prevent the leakage of the private key.Lemma 3.
LetV=v∈ℤm:v<t, σ=ωtlogm, and h:V⟶ℝ is a probability distribution. Then, for constant M=O1, the statistical distance of output distributions of Algorithms 1 and 2 is less than 2−ωlogm/M.Algorithm 1.
v←h, z←Dv,σm, output z,v with probability minDσmz/MDv,σmz,1.Algorithm 2.
v←h, z←Dσm, output z,v with probability 1/M.
Furthermore, the output probability of Algorithm 1 is at least1−2−ωlogm/M.


## 3. Security Model

In this section, we present our security model and define related security concepts.


### 3.1. LRS Definition

A LRS scheme consists of the following five PPT algorithms:(1)
Setup1λ: On input a security parameter λ, it outputs system public parameters PP.(2)
KeyGenPP: On input the public parameters PP, it outputs a public/private key pair pki,ski.We denote by SK and PK the domains of possible private and public keys, respectively.(3)
SignPP,L,m,skk: On input the public parameters PP, a public key list L, a message m∈0,1∗, and private key skk, it outputs a signature σm, which contains a linking tag I.(4)
VerifyPP,L,m,σm: On input the system public parameters PP, a public key list L, a message m∈0,1∗, and a signature σm, if σm is valid, it outputs “1”; otherwise, it outputs “0.”(5)
Linkσm1,σm2: On input two signatures σ1m1,σ2m2, where σ1m1 and σ2m2 are the signatures of different messages m1 and m2 under the same ring, which contain linking tags I1 and I2, respectively. It checks whether I1=?I2 and outputs “Link” if I1=I2; otherwise, it outputs “Unlink.” “Link” means that the two signatures are generated by the same signer, and “Unlink” means that the two signatures are generated by different signers.Definition 9 (correctness).
Correctness for LRS contains verification correctness and linking correctness simultaneously.(i)
Verification Correctness: For a valid signature σm, the probability of the algorithm VerifyPP,L,m,σm outputting “0” is negligible.(ii)
Linking Correctness: For two valid signatures σ1m1,σ2m2 generated by using the same private key, the probability of the algorithm Linkσm1,σm2 outputting “Unlink” is negligible. The formal definition of the correctness of the LRS scheme is shown in the following expressions:(8)Pr″0″←VerifyPP,L,m,σmPP←Setup1λpk,sk←KeyGenPPσm←SignPP,L,m,sk≤neglλ.(9)Pr“Unlink“←Linkσm1,σm2PP←Setup1λpk,sk←KeyGenPPσm1←SignPP,L1,m1,skσm2←SignPP,L2,m2,sk≤neglλ.


### 3.2. Security Model

Generally, a LRS scheme should satisfy three security properties, namely unforgeability, anonymity, and linkability. According to the security model of UALRS proposed by Liu et al. [8] in 2013, this study uses a series of games between an adversary A and a challenger S to describe the security model of LRS. Supposing there are l members in the ring, these three properties are described as follows:Before defining unforgeability, anonymity, and linkability, we consider the following oracles, which together simulate the adversary’s ability to break the security of the scheme.JO (Joining Oracle): A inputs member index k, and S outputs the corresponding public key pkk∈PK to ACO (Corruption Oracle): A inputs a public key pkk∈PK, which is a query output of JO, and S returns the corresponding private key skk∈SKSO (Signing Oracle): A inputs a public key list L=pki1≤i≤l∈PK, and a message m∈0,1∗, and S returns a valid signature σmIn addition, in the random oracle model, a random oracle modelHO is provided for users to query.


#### 3.2.1. Unforgeability

It means that users outside the ring cannot successfully forge a legal signature under the ring. That is, if there is no private key of a member in the ring, even if the adversary obtains multiple valid message signature pairs, the probability of the adversary forging a valid signature successfully is negligible. Unforgeability for the LRS scheme is defined by the following game between an adversaryA and a challenger S, in which A is given access to oracles JO, CO, SO, and HO:(i)
The system public parametersPP are generated by challenger S and given to A(ii)
A can access the oracles adaptively(iii)
A gives S a list L=pki1≤i≤l of public keys, a message m∈0,1∗, and a signature σmA wins the game if(i)
VerifyPP,L,m,σm=″1″(ii)
All public keys inL are obtained by querying JO(iii)
Any public key inL has not been input to CO(iv)
σm is not obtained by querying SOWe express it as(10)AdvAUnf=PrAwins the game.Definition 10 (unforgeability).
If the advantageAdvAUnf of any PPT adversary A to win the unforgeability game is negligible, then the LRS scheme is unforgeable.


#### 3.2.2. Unconditional Anonymity

It means that given a ring signature, no one can guess the real signer. In other words, given the public keys of all the members of the ring, it is impossible for anyone to tell the public key of the actual signer with a probability larger than1/l, where l denotes the cardinality of the ring, even the adversary has unlimited computing time and resources. The unconditional anonymity of LRS is described by the following game between an adversary A and a challenger S, where A is granted access to oracle JO:(i)
The system public parametersPP are generated by challenger S and given to A;(ii)
A can access the oracle JO adaptively;(iii)
A gives S a public key list L=pki1≤i≤l, which are query outputs of JO, and a message m∗∈0,1∗. S randomly samples b∈1,⋯,l, uses the signature key skb corresponding to pkb to run algorithm SignPP,L,m,skb, and generates and gives A the signature σm∗; and(iv)
A returns the guess value b′∈1,⋯,l.We express it as(11)AdvAAnon=Prb′=b−1/l.Definition 11 (unconditional anonymity).
If the advantageAdvAAnon of any unbounded adversary A to win the anonymity game is negligible, then the LRS scheme is called to be unconditional anonymous.
It is worth noting that though onlyJO is given to A, since A has unbounded computation power, it can calculate out the solution of any NP-hard problem, such as NTRU-SIS, large integer factorization, discrete logarithm, as well as the preimage of a given hash value. Therefore, unconditional anonymity in fact requires that in this case, A is still unable to reveal the pubic key of the actual signer of a RS with a probability higher than 1/l.


#### 3.2.3. Linkability

It means that two signatures generated by the same ring member can be linked. That is, an adversary who has less than two members’ private keys in the ring cannot generate two valid signatures determined by the linking algorithm as “Unlink.” The linkability of a LRS scheme is described by the following game between an adversaryA and a challenger S, where A is granted access to oracles JO, CO, SO, and HO:(i)
The system public parametersPP are generated by challenger S and given to A(ii)
A can access the oracles adaptively(iii)
A gives S two sets L1=pki1≤i≤l1 and L2=pki1≤i≤l2, messages m1,m2∈0,1∗, and signatures σm1 and σm2, where σm1 and σm2 contain the corresponding linking tags I1, I2, respectivelyA wins the game if(i)
All public keys inL1∪L2 are query outputs of JO(ii)
Fori=1,2, VerifyPP,Li,mi,σmi=″1″ such that σmi is not an output of SO(iii)
CO has been queried less than two times(iv)
Linkσm1,σm2=“Unlink“We express it as(12)AdvALink=PrAwins the game.Definition 12 (linkability).
If the advantageAdvALink of any PPT adversary A to win the linkability game is negligible, then the LRS scheme is linkable.


## 3.1. LRS Definition

A LRS scheme consists of the following five PPT algorithms:(1)
Setup1λ: On input a security parameter λ, it outputs system public parameters PP.(2)
KeyGenPP: On input the public parameters PP, it outputs a public/private key pair pki,ski.We denote by SK and PK the domains of possible private and public keys, respectively.(3)
SignPP,L,m,skk: On input the public parameters PP, a public key list L, a message m∈0,1∗, and private key skk, it outputs a signature σm, which contains a linking tag I.(4)
VerifyPP,L,m,σm: On input the system public parameters PP, a public key list L, a message m∈0,1∗, and a signature σm, if σm is valid, it outputs “1”; otherwise, it outputs “0.”(5)
Linkσm1,σm2: On input two signatures σ1m1,σ2m2, where σ1m1 and σ2m2 are the signatures of different messages m1 and m2 under the same ring, which contain linking tags I1 and I2, respectively. It checks whether I1=?I2 and outputs “Link” if I1=I2; otherwise, it outputs “Unlink.” “Link” means that the two signatures are generated by the same signer, and “Unlink” means that the two signatures are generated by different signers.Definition 9 (correctness).
Correctness for LRS contains verification correctness and linking correctness simultaneously.(i)
Verification Correctness: For a valid signature σm, the probability of the algorithm VerifyPP,L,m,σm outputting “0” is negligible.(ii)
Linking Correctness: For two valid signatures σ1m1,σ2m2 generated by using the same private key, the probability of the algorithm Linkσm1,σm2 outputting “Unlink” is negligible. The formal definition of the correctness of the LRS scheme is shown in the following expressions:(8)Pr″0″←VerifyPP,L,m,σmPP←Setup1λpk,sk←KeyGenPPσm←SignPP,L,m,sk≤neglλ.(9)Pr“Unlink“←Linkσm1,σm2PP←Setup1λpk,sk←KeyGenPPσm1←SignPP,L1,m1,skσm2←SignPP,L2,m2,sk≤neglλ.


## 3.2. Security Model

Generally, a LRS scheme should satisfy three security properties, namely unforgeability, anonymity, and linkability. According to the security model of UALRS proposed by Liu et al. [8] in 2013, this study uses a series of games between an adversary A and a challenger S to describe the security model of LRS. Supposing there are l members in the ring, these three properties are described as follows:Before defining unforgeability, anonymity, and linkability, we consider the following oracles, which together simulate the adversary’s ability to break the security of the scheme.JO (Joining Oracle): A inputs member index k, and S outputs the corresponding public key pkk∈PK to ACO (Corruption Oracle): A inputs a public key pkk∈PK, which is a query output of JO, and S returns the corresponding private key skk∈SKSO (Signing Oracle): A inputs a public key list L=pki1≤i≤l∈PK, and a message m∈0,1∗, and S returns a valid signature σmIn addition, in the random oracle model, a random oracle modelHO is provided for users to query.


### 3.2.1. Unforgeability

It means that users outside the ring cannot successfully forge a legal signature under the ring. That is, if there is no private key of a member in the ring, even if the adversary obtains multiple valid message signature pairs, the probability of the adversary forging a valid signature successfully is negligible. Unforgeability for the LRS scheme is defined by the following game between an adversaryA and a challenger S, in which A is given access to oracles JO, CO, SO, and HO:(i)
The system public parametersPP are generated by challenger S and given to A(ii)
A can access the oracles adaptively(iii)
A gives S a list L=pki1≤i≤l of public keys, a message m∈0,1∗, and a signature σmA wins the game if(i)
VerifyPP,L,m,σm=″1″(ii)
All public keys inL are obtained by querying JO(iii)
Any public key inL has not been input to CO(iv)
σm is not obtained by querying SOWe express it as(10)AdvAUnf=PrAwins the game.Definition 10 (unforgeability).
If the advantageAdvAUnf of any PPT adversary A to win the unforgeability game is negligible, then the LRS scheme is unforgeable.


### 3.2.2. Unconditional Anonymity

It means that given a ring signature, no one can guess the real signer. In other words, given the public keys of all the members of the ring, it is impossible for anyone to tell the public key of the actual signer with a probability larger than1/l, where l denotes the cardinality of the ring, even the adversary has unlimited computing time and resources. The unconditional anonymity of LRS is described by the following game between an adversary A and a challenger S, where A is granted access to oracle JO:(i)
The system public parametersPP are generated by challenger S and given to A;(ii)
A can access the oracle JO adaptively;(iii)
A gives S a public key list L=pki1≤i≤l, which are query outputs of JO, and a message m∗∈0,1∗. S randomly samples b∈1,⋯,l, uses the signature key skb corresponding to pkb to run algorithm SignPP,L,m,skb, and generates and gives A the signature σm∗; and(iv)
A returns the guess value b′∈1,⋯,l.We express it as(11)AdvAAnon=Prb′=b−1/l.Definition 11 (unconditional anonymity).
If the advantageAdvAAnon of any unbounded adversary A to win the anonymity game is negligible, then the LRS scheme is called to be unconditional anonymous.
It is worth noting that though onlyJO is given to A, since A has unbounded computation power, it can calculate out the solution of any NP-hard problem, such as NTRU-SIS, large integer factorization, discrete logarithm, as well as the preimage of a given hash value. Therefore, unconditional anonymity in fact requires that in this case, A is still unable to reveal the pubic key of the actual signer of a RS with a probability higher than 1/l.


### 3.2.3. Linkability

It means that two signatures generated by the same ring member can be linked. That is, an adversary who has less than two members’ private keys in the ring cannot generate two valid signatures determined by the linking algorithm as “Unlink.” The linkability of a LRS scheme is described by the following game between an adversaryA and a challenger S, where A is granted access to oracles JO, CO, SO, and HO:(i)
The system public parametersPP are generated by challenger S and given to A(ii)
A can access the oracles adaptively(iii)
A gives S two sets L1=pki1≤i≤l1 and L2=pki1≤i≤l2, messages m1,m2∈0,1∗, and signatures σm1 and σm2, where σm1 and σm2 contain the corresponding linking tags I1, I2, respectivelyA wins the game if(i)
All public keys inL1∪L2 are query outputs of JO(ii)
Fori=1,2, VerifyPP,Li,mi,σmi=″1″ such that σmi is not an output of SO(iii)
CO has been queried less than two times(iv)
Linkσm1,σm2=“Unlink“We express it as(12)AdvALink=PrAwins the game.Definition 12 (linkability).
If the advantageAdvALink of any PPT adversary A to win the linkability game is negligible, then the LRS scheme is linkable.


## 3.2.1. Unforgeability

It means that users outside the ring cannot successfully forge a legal signature under the ring. That is, if there is no private key of a member in the ring, even if the adversary obtains multiple valid message signature pairs, the probability of the adversary forging a valid signature successfully is negligible. Unforgeability for the LRS scheme is defined by the following game between an adversaryA and a challenger S, in which A is given access to oracles JO, CO, SO, and HO:(i)
The system public parametersPP are generated by challenger S and given to A(ii)
A can access the oracles adaptively(iii)
A gives S a list L=pki1≤i≤l of public keys, a message m∈0,1∗, and a signature σmA wins the game if(i)
VerifyPP,L,m,σm=″1″(ii)
All public keys inL are obtained by querying JO(iii)
Any public key inL has not been input to CO(iv)
σm is not obtained by querying SOWe express it as(10)AdvAUnf=PrAwins the game.Definition 10 (unforgeability).
If the advantageAdvAUnf of any PPT adversary A to win the unforgeability game is negligible, then the LRS scheme is unforgeable.


## 3.2.2. Unconditional Anonymity

It means that given a ring signature, no one can guess the real signer. In other words, given the public keys of all the members of the ring, it is impossible for anyone to tell the public key of the actual signer with a probability larger than1/l, where l denotes the cardinality of the ring, even the adversary has unlimited computing time and resources. The unconditional anonymity of LRS is described by the following game between an adversary A and a challenger S, where A is granted access to oracle JO:(i)
The system public parametersPP are generated by challenger S and given to A;(ii)
A can access the oracle JO adaptively;(iii)
A gives S a public key list L=pki1≤i≤l, which are query outputs of JO, and a message m∗∈0,1∗. S randomly samples b∈1,⋯,l, uses the signature key skb corresponding to pkb to run algorithm SignPP,L,m,skb, and generates and gives A the signature σm∗; and(iv)
A returns the guess value b′∈1,⋯,l.We express it as(11)AdvAAnon=Prb′=b−1/l.Definition 11 (unconditional anonymity).
If the advantageAdvAAnon of any unbounded adversary A to win the anonymity game is negligible, then the LRS scheme is called to be unconditional anonymous.
It is worth noting that though onlyJO is given to A, since A has unbounded computation power, it can calculate out the solution of any NP-hard problem, such as NTRU-SIS, large integer factorization, discrete logarithm, as well as the preimage of a given hash value. Therefore, unconditional anonymity in fact requires that in this case, A is still unable to reveal the pubic key of the actual signer of a RS with a probability higher than 1/l.


## 3.2.3. Linkability

It means that two signatures generated by the same ring member can be linked. That is, an adversary who has less than two members’ private keys in the ring cannot generate two valid signatures determined by the linking algorithm as “Unlink.” The linkability of a LRS scheme is described by the following game between an adversaryA and a challenger S, where A is granted access to oracles JO, CO, SO, and HO:(i)
The system public parametersPP are generated by challenger S and given to A(ii)
A can access the oracles adaptively(iii)
A gives S two sets L1=pki1≤i≤l1 and L2=pki1≤i≤l2, messages m1,m2∈0,1∗, and signatures σm1 and σm2, where σm1 and σm2 contain the corresponding linking tags I1, I2, respectivelyA wins the game if(i)
All public keys inL1∪L2 are query outputs of JO(ii)
Fori=1,2, VerifyPP,Li,mi,σmi=″1″ such that σmi is not an output of SO(iii)
CO has been queried less than two times(iv)
Linkσm1,σm2=“Unlink“We express it as(12)AdvALink=PrAwins the game.Definition 12 (linkability).
If the advantageAdvALink of any PPT adversary A to win the linkability game is negligible, then the LRS scheme is linkable.


## 4. Scheme Construction

(1)
Setup1λ,1n: On input the security parameter λ and integer n=2k, where k>0, a ring of l=ωlogn, a prime q=1mod2n, two parameters σ=1.17q/2n and s=0.585/πqln2+2/η, where η=2−λ/2n, choose a collision-resistant hash function H:0,1∗⟶0,1n, and output PP=q,σ,s,H.(2)
KeyGenPP: On input the system public parameters PP, the following steps should be performed:(i)
Run the trapdoor generation algorithmTrapGenn,q,σ to generate hi∈Rq,Bi∈ℤq2n×2n;(ii)
Randomly chooseti∈Rq, and let ski=si,0,si,1=SamplePreBi,s,ti such that si,0+si,1∗hi=ti,si,0,si,1≤s2n; and(iii)
Output a public key listL=hi1≤i≤l, and the private key for the member i: ski=si,0,si,1.(3)
SignPP,L,m,skk: On input the system public parameters PP, the public key list L=hi1≤i≤l, a message m∈0,1∗, and a private key skk=sk,0,sk,1, the member k performs the following steps:(i)
Compute linking tag(13)I=sk,0+sk,1∗hk.(ii)
For1≤i≤l, sample random vectors ri,0,ri,1←Dsn.(iii)
Let(14)v=H∑1≤i≤lri,0+ri,1∗hi,L,m,I.(iv)
Ifi≠k, compute(15)zi=zi,0,zi,1=ri,0,ri,1.ifi=k, compute(16)zk=zk,0,zk,1=sk,0∗v+rk,0,sk,1∗v+rk,1.(v)
Continue with probabilityminDsnzk/MDs∗v,snzk,1, where M=O1; otherwise restart.(vi)
Output signatureσm=m,zi1≤i≤l,v,I.(4)
VerifyPP,L,m,σm: On input the system parameters PP, the public key list L=hi1≤i≤l, a message m∈0,1∗, and a signature σm=m,zi1≤i≤l,v,I, output “1” if and only if the following conditions are true; otherwise, output “0”:(17)iv=H∑1≤i≤lzi,0+zi,1∗hi−Iv,L,m,I.(18)iiFor1≤i≤l,0≤zi,0,zi,1≤s2n.(5)
Linkσm1,σm2: On input two signatures σm1 and σm2, which contains linking tags I1 and I2, respectively, the following steps should be performed:Verify whetherI1=?I2. If I1=I2, then return “Link”; otherwise, return “Unlink.”Theorem 2 (correctness).
The proposed LRS scheme satisfies correctness.Proof.
Assumingσm=m,zi1≤i≤l,v,I is a signature generated by a member of the ring according to the algorithms under public key set L=hi1≤i≤l, then the following equation holds:(19)∑1≤i≤lzi,0+zi,1∗hi−Iv=zk,0+z∗k,1hk−Iv+∑1≤i≤l,i≠kzi,0+zi,1∗hi=sk,0+s∗k,1hkv+rk,0+rk,1∗hk−Iv+∑1≤i≤l,i≠kri,0+ri,1∗hi.
Given thatsk,0+s∗k,1hk=I, we have(20)∑1≤i≤lzi,0+zi,1∗hi−Iv=∑1≤i≤lri,0+ri,1∗hi.
Hence,(21)v=H∑1≤i≤lzi,0+zi,1∗hi−Iv,L,m,I.
By using the rejection sampling algorithm described in Definition8, the distribution of zi,0,zi,1 is close to Dsnzi for 1≤i≤l. Thus, by Lemma 3, we have zi=zi,0,zi,1 satisfies zi≤s2n with a probability at least 1−2−ωlogn. Therefore, the proposed scheme satisfies verification correctness.
Assume memberk calculates the linking tags of messages m1 and m2 as I1 and I2, respectively. In the proposed scheme, I1=sk,0+sk,1∗hk and I2=sk,0+sk,1∗hk are generated by the signer's public and private keys, and thus this scheme satisfies linking correctness. This completes the proof.


## 5. Security Analysis

Theorem 3 (unforgeability).
Under the random oracle model, when the e-NTRU problem is intractable, the proposed LRS scheme is unforgeable.Proof.
Setup Phase: To solve the e-NTRU problem, S gets an instance hi1≤i≤l
Query Phase: Adversary A is allowed to access oracles JO, CO, SO, and HO, and S responds as follows:(i)
H: A inputs ri,0,ri,11≤i≤l,L,m,I,k, S first checks whether there is the relevant record in the list listH. If so, then the same query result is returned to A. Otherwise, S randomly picks and gives A an integer v, and adds the tuple ri,0,ri,11≤i≤l,L,m,I,v,k to the list listH.(ii)
JO: Suppose A can only access the oracle JOl′ times at most, where l′≥l. S selects a subset Xl with l random indexes. S assigns hi1≤i≤l to these l indexes as their public keys, respectively. Moreover, for these l indexes, S does not know the corresponding private keys. We use l+1,⋅⋅⋅,l′ to denote other indexes. With regard to other l′−l indexes, S obtains the public and private keys according to the algorithm KeyGenPP. A inputs index j to query, and S outputs the corresponding public key.(iii)
CO: A inputs a public key pki=hi, S checks whether i belongs to Xl. If so, then S stops; otherwise, S outputs the corresponding private key.(iv)
SO: A inputs a ring public key set L=hi1≤i≤l, a public key hk, where k∈1,⋯,l, and a message m∈0,1∗. S performs as follows:(1)
Ifhk does not correspond to any element in the subset Xl, then S knows its private key and generates the signature according to the signature algorithm SignPP,L,m,skk. Otherwise, we assume that hk is obtained by JO.(2)
S checks the list listH to find the record ri,0,ri,11≤i≤l,L,m,I,v,k corresponding to the index k. Then, S randomly chooses zi,0,zi,1←Dsn and sets the output of H∑1≤i≤lzi,0+zi,1∗hi−Iv,L,m,I to v.(3)
S returns a signature σm=m,zi1≤i≤l,v,I with probability minDsnzk/MDsk∗v,snzk,1, where M=O1.
Forgery Phase: After the simulation, A gives signature σm∗=m∗,zi,0∗,zi,1∗1≤i≤l,v∗,I∗ about PP,m∗,L∗ to S satisfying the following conditions:(i)
VerifyPP,L∗,m∗,σm∗=″1″(ii)
All of the public keyspki=hi in L∗ are query outputs of JO(iii)
A did not query CO about the public keys in L∗(iv)
σm∗ is not a query output of SO
Analysis. Assuming the signature σm∗ is a valid signature, the following shows how S can solve the e-NTRU problem using the forged results of A. We will consider the following two situations:(i)
Ifv∗ appears in the SO, and assume that σm=m,zi,0,zi,11≤i≤l,v∗,I is a query output of SO. Given that the signature is valid, it satisfies(22)v∗=H∑1≤i≤lzi,0+zi,1∗hi−Iv∗,L,m,I.Given thatA successfully forged the signature, there is(23)v∗=H∑1≤i≤lzi,0∗+zi,1∗∗hi−I∗v∗,L∗,m∗,I∗.When the functionH collides, S aborts (Abort I). Otherwise, from (22) and (23), there is(24)L∗=L,m∗=m,I∗=I,∑1≤i≤lzi,0+zi,1∗hi−Iv∗=∑1≤i≤lzi,0∗+zi,1∗∗hi−I∗v∗.(25)∑1≤i≤lzi,0−zi,0∗+zi,1−zi,1∗∗hi=0modq.Therefore,zi,0∗−zi,0,zi,0∗−zi,11≤i≤l is a solution to the e-NTRU problem.(ii)
Ifv∗ appears in the H query and is stored as ri,0,ri,11≤i≤l,L,m,I,v∗,k in listH, then,(26)v∗=H∑1≤i≤lri,0+ri,1∗hi,L,m,I.When the functionH collides, S aborts (Abort II). Otherwise, from (23) and (26), there is(27)L∗=L,m∗=m,I∗=I,∑1≤i≤lzi,0∗+zi,1∗∗hi−I∗v∗=∑1≤i≤lri,0+ri,1∗hi.S performs the following: when i≠k∗, let zi,0=ri,0 and zi,1=ri,1; when i=k∗, let zk∗,0=rk∗,0+v∗I and zk∗,1=rk∗,1. Then, we have(28)v∗=H∑1≤i≤lri,0+ri,1∗hi,L,m,I=H∑1≤i≤l,i≠k∗ri,0+ri,1∗hi+zk∗,0−v∗I+zk∗,1∗hk∗,L,m,I=H∑1≤i≤lri,0+ri,1∗hi−v∗I,L,m,I.Given (23), (27), and (28), we have(29)∑1≤i≤lzi,0−zi,0∗+zi,1−zi,1∗∗hi=0modq.Thus, the solution to the e-NTRU problem iszi,0∗−zi,0,zi,0∗−zi,11≤i≤l.
Probability Analysis. The challenger S fails when Aborts I and II occur. The probability of H colliding is 1/2n. Assume A can successfully forge the signature with probability ξ, then the probability of S solving the e-NTRU problem is ξ−1/2n×2=ξ−1/2n−1. This completes the proof.Theorem 4 (unconditional anonymity).
The proposed scheme satisfies unconditional anonymity.Proof.
The anonymity proof of the signature is completed by the following game between adversaryA and challenger S. If the signature distributions of l different members in the ring are computationally indistinguishable to adversary A, then this scheme satisfies anonymity.Query Phase: A is allowed to access JO, and S responds as follows:JO: A inputs an index j to query. S runs the algorithm KeyGenPP to generate the public key pkj=hj and returns it to A.Challenge Phase: A inputs a public key list L=hi1≤i≤l, and a message m∗∈0,1∗. S randomly chooses b∈1,⋯,l, then runs SignPP,L,m∗,skb to generate the signature σm∗=SignPP,L,m∗,skb and gives it A, where skb is the private key corresponding to index b.Guess Phase: A gives a value b′∈1,⋯,l as a guess for b.Analysis. Suppose A is an adversary with unlimited computing power. Next, we will show the advantage AdvAAnon of A in winning the anonymous game is negligible. We need to prove that the distributions of signatures generated with the private keys of different users are computationally indistinguishable.
First, evenA is an adversary with unlimited computing power, from the JO query, or from the challenger signature (which contains a linkability tag), A still cannot deduce the private key, as well as the corresponding index. That is because the randomness of the algorithms TrapGen and SamplePre makes each public key hb correspond to multiple pairs sb,0,sb,1, and which one is the actual private key of member b cannot be determined. Moreover, given a linking tag I=sb,0+sb,1∗hb, to know which member generated the linking tag I, it is no better than random guessing for the adversary. In addition, it should be noticed that the signature σm∗ is generated by using not only a private key sb,0,sb,1 but also a set of random numbers. Lemma 3 guarantees that the distributions of zb,0,zb,1 and zi,0,zi,1i≠b are indistinguishable, and the distribution of zb,0,zb,1 is independent of sb,0,sb,1. That is, in the view of the adversary, the signature σm∗ is independent of the index b of the actual signer. Hence, we can conclude that even an unbounded adversary cannot guess the index b with a probability greater than 1/l.
We can infer that whenA is a normal adversary, that is, A has limited computing power and time, obviously it ccannot destroy the anonymity of the scheme. This completes the proof.Theorem 5 (linkability).
Under the random oracle model, if the proposed scheme is unforgeable, then for any PPT adversaryA, the proposed scheme is linkable.Proof.
We will show that if the proposed scheme satisfies unforgeability, then it will satisfy linkability. The linkability proof of the scheme is completed by the following game interaction between an adversaryA and a challenger S.(i)
S generates the system public parameters PP and public and private keys pki,ski1≤i≤l, and then sends PP to A(ii)
A can access JO, CO, SO, and HO, and the process of accessing JO, CO, SO, and HO in the linkability game is the same as that in the unforgeability game(iii)
SupposeA outputs two signatures σ1m1=m1,zi,0,zi,11≤i≤l,v1,I1 and σ2m2=m2,zi,0′,zi,1′1≤i≤l,v2,I2 under public key set L, which satisfy the following conditions:(1)
All public keys inL are outputs of JO(2)
Fori=1,2, VerifyPP,L,mi,σimi=″1″ such that σimi is not an output of SO(3)
A accesses CO once at most
Analysis. Assume A can generate two signatures σ1m1 and σ2m2 with a nonnegligible probability η while holding only one private key skk, and ″1″←VerifyPP,L,mi,σimi for i=1,2. Given that the proposed LRS scheme is unforgeable, these two signatures can be validated by the Verify algorithm if and only if A honestly generates signatures σ1m1 and σ2m2 using his private key skk. In other words, we have I1=sk,0+sk,1∗hk and I2=sk,0+sk,1∗hk′. And since there is also only one public key corresponding to this private key, that is, hk=hk′, we have I1=I2. This indicates that the algorithm Linkσ1m1,σ2m2 returns “Link“ when given two signatures σ1m1 and σ2m2. Hence, the advantage AdvAlink of A is negligible. This completes the proof.


## 6. Discussion

### 6.1. Parameter Selection

The security of the proposed scheme is based on the e-NTRU problem, which is reduced to the NTRU-SIS problem. The NTRU-SIS problem is to find two polynomialsu,v∈Rq2 that satisfies u+v∗h=0modq and u,v≤β in the NTRU lattice, which is in turn reduced to γ-Ideal-SVP problem. Similar to [34, 36], we use the “root Hermite factor γ” which measures the hardness of γ-Ideal-SVP problems to select the parameters.If we look for a polynomialv in an n-dimensional lattice, which is greater than the n-th root of the determinant, then the associated γ is(30)vdetΛ1/n=γn.According to [37], if we look for a small-size polynomial v in the NTRU lattice, the associated γ is(31)n/2πe⋅detΛ1/nv=0.4γn.From the results in [36, 38], if the value of γ is approximately 1.007, to find the polynomial is at least 80 bits hard. If the value of γ is less than 1.004, to find the polynomial is at least 192 bits hard.The methods to attack the proposed scheme are mainly to attack the ring member's public key and the signature.The public key of the memberi is a polynomial hi=gi∗fi−1modq∈Rq. The attack on hi is to find two nonzero small-size polynomial ui,vi∈Rq2 that satisfies ui+vi∗hi=0modq. By Lemma 1 we know, ui,vi≤σ2n. So using (32) to calculate the value of γ, we have γ=n/1.3681/2n. When n=256, γ≈1.0048, it is at least 80 bits hard to attack the ring member's public key, and when n=512, γ≈1.0027, it is at least 192 bits hard to attack the ring member’s public key.The attack on the signature of the memberi is to find a vector zi,0,zi,1 passing the verification algorithm without member i′s private key. It can be seen from Lemma 3, zi,0,zi,1≤s2n. Since s=0.585/πqln2+2/η, where η=2−λ/2n, there is s=1.4708q for n=256 and s=2.2089q for n=512. So, computing the value of γ by (28), we have(32)σ2nq=γ2n⟹γ=2.080n1/2n,n=256γ=3.124n1.2nn=512.Whenn=256, γ≈1.0069, to attack the ring member’s signature is at least 80 bits hard, and when n=512, γ≈1.0041, to attack the ring member's signature is at least 192 bits hard. The recommended choice of the parameters is shown in Table 2.Table 2
Parameter settings.
ParameterRecommended choiceλ80192γ1.00691.0040n256512


### 6.2. Post-Quantum Security

The proposed scheme is based on the hard assumption over lattice which is generally recognized to provide anti-quantum security. The security proof of the proposed scheme is unlikely to be extended to the Quantum Random Oracle Model [39] (QROM): in the security proof (Theorems 3 and 5), we use the adaptive programming of random oracle (RO) H, and this proof technique is inherent in the structure to some extent.We note that other schemes built on QROM, such as [40, 41], also use the form of RO programming (even if not adaptive). In addition, although Fiat–Shamir seems unlikely to be proved in QROM, to the best of our knowledge, there are no attacks on the protocols using these proof technologies, which stems from the use of RO.


## 6.1. Parameter Selection

The security of the proposed scheme is based on the e-NTRU problem, which is reduced to the NTRU-SIS problem. The NTRU-SIS problem is to find two polynomialsu,v∈Rq2 that satisfies u+v∗h=0modq and u,v≤β in the NTRU lattice, which is in turn reduced to γ-Ideal-SVP problem. Similar to [34, 36], we use the “root Hermite factor γ” which measures the hardness of γ-Ideal-SVP problems to select the parameters.If we look for a polynomialv in an n-dimensional lattice, which is greater than the n-th root of the determinant, then the associated γ is(30)vdetΛ1/n=γn.According to [37], if we look for a small-size polynomial v in the NTRU lattice, the associated γ is(31)n/2πe⋅detΛ1/nv=0.4γn.From the results in [36, 38], if the value of γ is approximately 1.007, to find the polynomial is at least 80 bits hard. If the value of γ is less than 1.004, to find the polynomial is at least 192 bits hard.The methods to attack the proposed scheme are mainly to attack the ring member's public key and the signature.The public key of the memberi is a polynomial hi=gi∗fi−1modq∈Rq. The attack on hi is to find two nonzero small-size polynomial ui,vi∈Rq2 that satisfies ui+vi∗hi=0modq. By Lemma 1 we know, ui,vi≤σ2n. So using (32) to calculate the value of γ, we have γ=n/1.3681/2n. When n=256, γ≈1.0048, it is at least 80 bits hard to attack the ring member's public key, and when n=512, γ≈1.0027, it is at least 192 bits hard to attack the ring member’s public key.The attack on the signature of the memberi is to find a vector zi,0,zi,1 passing the verification algorithm without member i′s private key. It can be seen from Lemma 3, zi,0,zi,1≤s2n. Since s=0.585/πqln2+2/η, where η=2−λ/2n, there is s=1.4708q for n=256 and s=2.2089q for n=512. So, computing the value of γ by (28), we have(32)σ2nq=γ2n⟹γ=2.080n1/2n,n=256γ=3.124n1.2nn=512.Whenn=256, γ≈1.0069, to attack the ring member’s signature is at least 80 bits hard, and when n=512, γ≈1.0041, to attack the ring member's signature is at least 192 bits hard. The recommended choice of the parameters is shown in Table 2.Table 2
Parameter settings.
ParameterRecommended choiceλ80192γ1.00691.0040n256512


## 6.2. Post-Quantum Security

The proposed scheme is based on the hard assumption over lattice which is generally recognized to provide anti-quantum security. The security proof of the proposed scheme is unlikely to be extended to the Quantum Random Oracle Model [39] (QROM): in the security proof (Theorems 3 and 5), we use the adaptive programming of random oracle (RO) H, and this proof technique is inherent in the structure to some extent.We note that other schemes built on QROM, such as [40, 41], also use the form of RO programming (even if not adaptive). In addition, although Fiat–Shamir seems unlikely to be proved in QROM, to the best of our knowledge, there are no attacks on the protocols using these proof technologies, which stems from the use of RO.


## 7. Performance Analysis

In this section, the proposed LRS scheme is compared with the schemes [23, 24, 26, 27, 30] in terms of efficiency. We mainly compare these schemes in terms of elapsed time and storage space.Comparison terms in Table3 include signature generation cost, signature verification cost, unconditional anonymity, and difficult assumption. Comparison terms in Table 4 include public and private key, as well as signature size of each user. In Tables 3 and 4, n is the degree of polynomials, q=1mod2n is a large prime number, l represents the cardinality of the ring, and k and v are integers. The time cost for the discrete Gaussian sampling algorithm and the rejection sampling algorithm running once are represented by TSD and TRS, respectively. In general, TSD>TRS. The time cost for polynomial-polynomial multiplication is represented by TMul, and TMul>TSD. The time overhead of hash, matrix-matrix addition, and polynomial-polynomial addition is ignored because these operations take less time. We mainly focus on time-consuming operations, such as matrix-matrix multiplication and polynomial-polynomial multiplication.Table 3
Comparison of time costs and difficult assumption.
SchemeSignature costVerification costUnconditional anonymityDifficult assumption[23]nlTSD+kn2l−1TMul+nTRS2knlTMulNoMSIS, MLWE[24]knlTSD+k2n2l+1TMul+knTRS2k2nlTMulYesR-SIS[26]knlTSD+kn2l+1TMul+knTRS2knlTMulNoMSIS, MLWE[27]vnTSD+5knTMullogl2knTMulloglNoMSIS, MLWE[30]2nl+1TSD+2nl+1TMul2nlTMulNoR-SIS,R-ISISOurs2nlTSD+nlTMul+2nTRSnlTMulYese-NTRUTable 4
Comparison of communication costs.
SchemePublic key size (bits)Private key size (bits)Signature size (bits)[23]knlogqnlogqOn⋅l[24]nlogqknlogqOkn⋅l[26]3knlogqknlogqOkn⋅l[27]kvnlogqvnlogqOn⋅logl[30]nlogq9nlogqOn⋅lOursnlogq2nlogqOn⋅lIn terms of signature generation cost, the proposed scheme mainly uses the Gaussian sampling algorithm2l times, the polynomial-polynomial multiplication l times, and the rejection sampling algorithm once, respectively. Hence, the signature generation cost is 2nlTSD+nlTMul+2nTRS. In terms of signature verification cost, since the proposed scheme primarily runs polynomial-polynomial multiplication l times, the signature generation cost is about nlTMul. From Table 3, due to TMul>TSD>TRS, compared with the four schemes of [23, 24, 26, 30], the proposed scheme has higher signature generation and verification efficiency. The signature generation and verification time of the proposed scheme is linearly related to the number of ring members l, while that of the scheme of [27] has a logarithmic relationship with l. Therefore, when l is large, the signature generation and verification efficiency of the scheme of [27] is better than that of the proposed scheme. But when l is small, the proposed scheme is more efficient by the settings of relevant parameters. In addition, only Alberto Torres et al.’s scheme [24] and our scheme can achieve unconditional anonymity, while other four schemes only have computational anonymity. And the efficiency of signature generation and verification of our scheme is obviously higher than that of Torres et al.’s scheme.In the proposed scheme, the public key of the member in the ring is a small polynomialhi∈Rq generated by the trapdoor generation algorithm TrapGen, and the private key corresponds to two small polynomials in Rq. Therefore, the public and private key lengths of the proposed scheme are nlogq and 2nlogq, respectively. As shown in Table 4, the public and private key lengths of [23, 24, 26, 27, 30] are knlogq,nlogq, nlogq,knlogq, 3knlogq,knlogq, kvnlogq,vnlogq, and nlogq,9nlogq, respectively. Hence, in terms of public key size, the public key size of the proposed scheme is similar to that of [24, 30] and smaller than that of [23, 26, 27]. With respect to private key size, the private key size of the proposed scheme is larger than that of [23] and they are both smaller than that of [24, 26, 27, 30]. For signature size, the signature size of the scheme [27] has a logarithmic relationship with l, while that of the other five schemes including the proposed scheme has a linear relationship with l. But the growth rate of signature size of [23, 30] and the proposed scheme is obviously slower than that of [24, 26].


## 8. Implementation and Evaluation

We implemented and evaluated the proposed LRS scheme on a typical laptop configured with a Windows 8.1 system, an Intel(R) Core(TM) i5-4210U CPU@1.70 GHz processor, and a 4.00 GB running memory. We selected parameters to make the proposed scheme secure, and detailed parameter settings are given in Table5. We ran the signature generation and verification algorithms for 1000 times. And at security level λ=80, the average running time of these algorithms of the five schemes under different numbers of ring members is shown in Table 6. It can be seen from Table 6 that the signature generation and verification of [24] take the longest time among the six schemes, while the signature generation and verification time of the proposed scheme is shorter than that of [23, 24, 26, 30]. Compared with [27], when l≤256, the proposed scheme has higher signature efficiency, but when l≥512, the signature efficiency of the proposed scheme needs to be improved. On average, compared with the other five schemes, the signature generation and verification time of the proposed scheme is reduced by about 56.61% and 65.18%, respectively. Especially compared with [24], which also has unconditional anonymity as ours, the signature generation and verification time of the proposed scheme is reduced by about 94.52% and 97.18%, respectively.Table 5
Parameter settings for our scheme.
ParameternkvqSecurity levelRecommended choice2565423280 bitsTable 6
Comparison of time costs (ms) at security levelλ=80.
SchemeSignature timeVerification timel=1l = 8l = 64l = 128l = 256l = 512l = 1024l = 2048l = 1l = 8l = 64l = 128l = 256l = 512l = 1024l = 2048[23]3.4233.44218.09421.31817.841532.272953.145666.395.7335.46200.10379.92750.351410.442699.055189.23[24]32.87154.361019.571906.383693.687084.9214018.5627925.3124.32133.12950.271769.473440.646619.1413120.3123855.36[26]9.2548.87282.71525.431002.421890.293659.717106.845.6336.86201.19389.94753.651428.682752.515295.31[27]34.97101.14202.98239.61281.36330.24381.64447.1214.0241.5683.32100.15121.06150.38176.86237.63[30]3.7814.8882.87151.91265.57514.81986.621898.851.237.7849.8194.37162.53316.15622.341172.31Ours1.7110.3659.56109.04199.47364.63688.641367.060.734.6329.1349.8194.37162.53316.15622.34At security levelλ=80, the comparison between the proposed scheme and the other five schemes on public/private key size and signature size under different numbers of ring members is shown in Table 7. As for the public key size, the public key size of the proposed scheme is equal to that of [24, 30] and smaller than that of [23, 26, 27]. With respect to private key size, the private key size of the proposed scheme is larger than that of [23] but is significantly smaller than that of [24, 26, 27, 30]. In the case of signature size, the signature size of the proposed scheme is larger than that of [23] but is significantly smaller than that of [24, 26, 30]. When l≥64, the signature size of the scheme in [27] is shorter than that of the proposed scheme. However, the scheme of [27] only has computational anonymity, while the proposed scheme has unconditional anonymity. Especially compared with [24], the signature size of the proposed scheme is reduced by 58.03% on average.Table 7
Comparison of storage overhead (KB) at security levelλ=80.
Scheme[23][24][26][27][30]OursSize of public key5.451.0916.3531.801.091.09Size of private key1.095.455.456.369.812.18Signature size forl = 16.546.547.6333.394.363.27Signature size forl = 814.1744.6945.7836.5727.2518.53Signature size forl = 6475.21349.89350.9841.34210.37140.61Signature size forl = 128144.97698.69699.7842.93419.65280.13Signature size forl = 256284.491396.291397.3844.52838.21559.17Signature size forl = 512563.532791.492792.5846.111675.331117.25In addition, in the above experiment, we only completed the proof-of-concept work and did not consider potential optimization algorithms, such as the polynomial-polynomial multiplication based on FFT.


## 9. Conclusions

Based on the e-NTRU problem, this study constructed a LRS scheme on NTRU lattice by combining preimage and rejection sampling techniques. Under the random oracle model, the security of our LRS scheme was analyzed in detail. The analysis results show that our scheme satisfies the requirements of correctness, unforgeability, and linkability based on the intractability of the e-NTRU problem in the random oracle model. In particular, our scheme can achieve unconditional anonymity. The efficiency of the proposed scheme was analyzed in detail, and the optional parameter settings of the proposed scheme that meet the security requirements are given. Finally, the proposed scheme and other five latest lattice-based LRS schemes are implemented, which shows that under the same security level, the proposed scheme has higher signature generation and verification efficiency as well as shorter signature size compared with other five LRS schemes.



---

*Source: 8431874-2022-05-13.xml*