# Efficient Lattice-Based Ring Signature Scheme without Trapdoors for Machine Learning

Authors: Qing Ye; Yongkang Lang; Zongqu Zhao; Qingqing Chen; Yongli Tang
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

Machine learning (ML) and privacy protection are inseparable. On the one hand, ML can be the target of privacy protection; on the other hand, it can also be used as an attack tool for privacy protection. Ring signature (RS) is an effective way for privacy protection in cryptography. In particular, lattice-based RS can still protect the privacy of users even in the presence of quantum computers. However, most current lattice-based RS schemes are based on a strong trapdoor like hash-and-sign, and in such constructions, there is a hidden algebraic structure, that is, added to lattice so that the trapdoor shape is not leaked, which greatly affects the computational efficiency of RS. In this study, utilizing Lyubashevsky collision-resistant hash function over lattice, we construct an RS scheme without trapdoors based on ideal lattice via Fiat‒Shamir with aborts (FSwA) protocol. Regarding security, the proposed scheme satisfies unconditional anonymity against chosen setting attacks (UA-CSA), which is stronger than anonymity against full key exposure (anonymity-FKE), and moreover, our scheme satisfies unforgeability with respect to insider corruption (EU-IC). Regarding computational overhead, compared with other RS schemes that satisfy the same degree of security, our scheme has the highest computational efficiency, the signing and verification time costs of the proposed scheme are obviously better than those of other lattice-based RS schemes without trapdoors, which is more suitable for ML scenarios.


---

## Body

## 1. Introduction

Machine learning (ML) and privacy protection are inextricably linked. On the one hand, ML itself requires privacy protection, i.e., the training datasets and models in ML systems should not be disclosed. On the other hand, ML can also be an attack tool for privacy protection, and how to protect users’ sensitive information is a challenging task under the increasingly powerful ML technology.Ring signature (RS), introduced by Rivest et al. [1] in 2001, is an effective technique for privacy protection in cryptography, which on the one hand enables the recipient of the data to believe that the source of the data is reliable, and on the other hand, obscures the identity of the data owner so that the recipient cannot be sure who is the real owner of the data. In an RS scheme, each user has a public key, and the signer can autonomously collect user’s public keys to form a ring without the permission or assistance of other users (where the signer is contained in the set of ring members), and the verifier only knows that the signature was generated under the ring, but is unsure which member’s private key is used as the signing key. Due to the anonymity of RS, it is widely used in fields such as e-voting, anonymous membership authentication, and anonymous tip-off.Since the seminal work of [1], the research on RS has been unprecedentedly active. A general framework for constructing 1-out-of-n signature schemes was introduced by Abe et al. [2], which can use different types of keys to construct signatures based on integer decomposition and discrete logarithm problems. After that, many RS schemes along with their associated authentication schemes [3–10] have been proposed. However, the security definitions of these RS schemes are weak, i.e., they have not considered for certain realistic attacks. Bender et al. [11] proposed new definitions of anonymity and the unforgeability of RS to cover these attacks. Bender et al. [11] divided anonymity into three levels according to the degree of security, where the strongest version is anonymity against full key exposure (Anonymity-FKE), i.e., even if adversary is given the private keys of all ring members, the adversary is still unable to guess who is the genuine signer of the given RS. Regarding existential unforgeability, there are also three levels: unforgeability against fixed-ring attacks (EU-FRA), unforgeability against chosen-subring attacks (EU-CSA), and unforgeability with respect to insider corruption (EU-IC). Based on EU-CSA, the strongest EU-IC means the adversary cannot succeed in forging a signature, even if the adversary is allowed to obtain the private keys of ring members via asking a corruption oracle.Most previous RS schemes [1–7, 9–11] are constructed under the assumptions of classical number theory, which are hardly resistant to quantum attacks [12]. In 1996, Ajtai [13] introduced the algebraic structure of lattice into cryptographic schemes. In the postquantum era, the new cryptosystem based on lattice has become a focus of research due to its merits of high asymptotic efficiency, simple operation, parallelizability, resistance to quantum attacks, and enjoying the average-to-worst reduction. The development of lattice-based provably secure encryption has developed rapidly and has made great progress [14–18], while lattice-based digital signature has experienced a tortuous and bumpy process in the earlier years. First, Goldreich et al. [19] made an attempt at a lattice-based signature, then NTRU signature was proposed by Hoffstein et al. [20], and it was repaired and enhanced in [21, 22]. However, these digital signature schemes [19, 20, 22] on lattice failed to be proved secure under the attacks of [23, 24]. To date, provably secure signature schemes on lattice can be divided into two main branches: schemes with trapdoors and without trapdoors. Digital signature schemes with trapdoors started from the “hash-and-sign” signature scheme constructed by Gentry et al. [25] based on SIS assumption, which is also the first lattice-based signature scheme, that is, provably secure. and Peikert [26] improved the structure of trapdoors, that is, proposed by [27], proposed the concept of G trapdoors on lattice, and remarkably improved the computational efficiency of trapdoor generation algorithm on lattice. A digital signature scheme on an ideal lattice was proposed by Ducas and Micciancio [28], and its trapdoor is constructed utilizing the technique of [26]. These trapdoors are deemed to be very suitable for lattice-based signature schemes, but the lattice is added with a hidden algebraic structure, which significantly affects the efficiency of signature schemes and is a payment that has to be considered. Digital signature schemes on lattice without trapdoors are mainly based on Stern’s zero-knowledge proofs. Although the Stern-type protocol is powerful, the soundness error of a single execution of the protocol is 2/3. Such protocol needs to be repeated many times so that the soundness error drops to a negligible value, so it is difficult to further improve their efficiency. To the best of our knowledge, only Lyubashevsky signature schemes [29, 30] without trapdoors are constructed not based on the Stern-type protocol, but on the Fiat‒Shamir with aborts (FSwA) protocol, via which a very efficient digital signature scheme on lattice could be constructed.Similar to a digital signature over lattice, lattice-based (linkable) RS can also be mainly divided into two branches, i.e., with trapdoors and without trapdoors. Lattice-based RS schemes with trapdoors have been extensively studied [31–36]. Notice that these lattice-based RS schemes with trapdoors, although are progressing about storage overhead, cannot always avoid the drawbacks brought by the structure of hash-and-sign, and the computational efficiency cannot be enhanced to a satisfactory level. Lattice-based RS schemes without trapdoors can be classified into membership proofs-based schemes and FSwA-based schemes. Several RS schemes [37–40] based on membership proofs have been proposed. Such RS schemes usually first construct a membership proof which is generally a zero-knowledge proof and then construct an RS scheme based on this proof. The efficiency of these RS schemes directly depends on that of underlying zero-knowledge proofs, which have the advantage that the signature length is usually OlogN, where N is the ring size, whereas the disadvantage is also obvious, i.e., the large and complex zero-knowledge proofs lead to low computational efficiency, and the length of RS could be large when N is small. (Linkable) RS schemes [41–44] based on FSwA are rather efficient in terms of computational efficiency, with the drawback that the signature length is common ON, yet it is very suitable in small-scale scenarios. For RS on lattice, several schemes [37–40] can satisfy the strongest Anonymity-FKE and EU-IC defined by Bender et al. [11]. In fact, Aguilar Melchor et al. [41] defined stronger anonymity, i.e., unconditional anonymity against chosen setting attacks (UA-CSA), and inspired by Lyubashevsky signature scheme [29], Aguilar Melchor et al. [41] constructed two RS schemes (AM1 and AM2) utilizing lattice-based collision-resistant hash function h∈HD,Dx,m [45], both of which can achieve UA-CSA for anonymity; regarding unforgeability, AM1 and AM2 satisfy EU-CSA and EU-IC, respectively. However, we deem that Aguilar Melchor et al. do not make good use of h∈HD,Dx,m in transforming Lyubashevsky digital signature [29] into RS, which causes the storage and computational overheads of both schemes of Aguilar Melchor et al. [41] to be large. In this work, via the FSwA protocol, we redesign an RS scheme on lattice without trapdoors using h∈HD,Dx,m again, the main contributions are as follows:(1)
Different from the RS schemes of Aguilar Melchor et al. [41] on lattice, in our key generation algorithm, the input value of h∈HD,Dx,m is taken as a user’s private key, the output value of h∈HD,Dx,m is taken as a public key, that is, relevant to the private key, which makes the length of a public key is reduced from a polynomial vector of m dimensions to a polynomial. Our signing algorithm is designed based on the framework of the RS scheme of Abe et al. [2], which is based on the discrete-log assumption, and the proposed scheme will be more concise and efficient.(2)
Under the improved security model of Aguilar Melchor et al. [41], the proposed RS scheme is rigorously proven to be safe. Regarding anonymity, our scheme satisfies the strongest UA-CSA; in terms of unforgeability, our scheme satisfies the strongest EU-IC. And under the random oracle model, the unforgeability of the proposed scheme could be reduced to the approximate shortest vector problem SVPγ over ideal lattice.(3)
Finally, with respect to performance and security, the proposed scheme is comprehensively compared with several schemes [37, 38, 40, 41]. The results show that compared with AM1 and AM2 of [41], the storage and computational overhead of our scheme are significantly reduced. In addition, compared with the computational overhead of other schemes, our scheme is remarkably superior, and is more suitable for ML applications.


## 2. Preliminaries

### 2.1. Notations

The symbolN represents the abbreviation of the set 1,2,…,N. Let R be the set of real numbers, R+ be the set of positive real numbers, and Z be the set of integers. For a finite set S, the symbol y←S denotes a random uniform sampling from S. The upper-case letter X is the random variable denoting a signature, and X←F denotes X as the output of the signature algorithm F. Vectors and matrices are denoted by lower-case e.g.,x and upper-case e.g.,X letters in italic & bold, respectively. In this work, we construct a cryptographic scheme on ring D=Zqx/xn+1, where xn+1 is an irreducible polynomial, and all logarithms we use are base 2. Zq is the set of integers modulo q, elements in Zq are denoted by integers selected from the interval −q−1/2,q−1/2, and then the elements in D are represented by n−1 degree polynomials whose coefficients are taken from Zq. For a=∑ifixi∈D, the common norms of a are given as follow:(1)l1:a1=∑ifi,l2:a2=∑ifi21/2,l∞:a∞=maxifi.For a polynomial vectora=a1,a2,…,am, where a1,a2,…,am∈D,m is a positive integer, and the infinite norm with respect to a is defined as follows:(2)a∞=maxiai∞.Additionally, we will use the following notations:(3)Dc=g∈D:g∞≤1,Ds=g∈D:g∞≤nlogn,Dx=g∈D:g∞≤mn1.5logn+nlog2n,Dy=g∈D:g∞≤mn1.5logn,Dz=g∈D:g∞≤mn1.5logn−nlog2n.The complexity of algorithms is measured using the standard asymptotic notationsω,O:(4)fn=ωgniflimn⟶∞fngn=∞,fn=Ogniflimn⟶∞fngn≠∞.Use the symbolO˜ to suppress poly-logarithmic factors, and for example, for any constant c and c′, fn=Onclogc′n, we have fn=O˜nc.


### 2.2. Lattice and Ideal Lattice

Micciancio [46] first proposed the concept of cyclic lattice, which to a certain extent eliminated the drawbacks of big key size and operational inefficiency of cryptographic schemes on Euclidean lattice. Lyubashevsky and Micciancio [45] first proposed the definition of an ideal lattice, which is a lattice with a special algebraic structure and is a generalization of the cyclic lattice. In general, a Euclidean lattice is a subgroup of a group, and an ideal lattice is an ideal of a ring.Definition 1.
(lattice). Supposing matrixB is composed of a set of linearly independent vectors b1,b2,…,bm∈Zn , then the integer lattice generated by B is defined as:(5)LO=Bx=∑xibi:x∈Zm,b1,b2,…,bm form a set of bases over LB. In short, LB is a discrete additive subgroup in the n-dimensional real space Rn.Definition 2.
(q-ary lattice). Given a prime q, positive integers m, n, for any matrix A∈Zqn×m, the integer lattice, that is, m-dimensional full-rank is described as follows:(6)Λ⊥A=u∈Zms.t.Au=0modq.Definition 3.
(ideal lattice). Letf be a monic irreducible polynomial of degree n, the ideal I⊆Zx/f, then an integer lattice LB⊆Zn such that LB=gmodf:g∈I is called an ideal lattice.


### 2.3. Hardness Assumption

Definition 4.
(R-SISq,m,β problem). Given a randomly chosen vector a∈Dm, find the vector x∈Dm such that aT⋅x=0 satisfying 0<x2≤β, where q, m are positive integers, β∈R+.Definition 5.
(SVPγ). Given a lattice LB and an approximation factor γ≥1, find a nonzero vector v on lattice such that v∞≤γu∞ holds for any vector u∈LB.


### 2.4. Collision-Resistant Hash Functions and Boundingacmodxn+1∞

Lyubashevsky and Micciancio [45] defined a family of collision-resistant hash functions on ideal lattice, which are efficient functions based on the hardness of worst-case lattice problems, and showed that finding collisions for h∈HD,Dx,m is at least as hard as solving SVPγ, where γ=O˜n2.Definition 6.
(family of hash functions). For any integerm and set Dx, the family of hash functions HD,Dx,m=ha:a∈Dm, where a hash function ha:Dxm⟶D. On input polynomial vectors b=b1,b2,…,bm∈Dxm, then hab=a⋅b=a1b1+a2b2+⋯+ambm. There are two homomorphic properties about h∈HD,Dx,m as follows:(7)hx+y=hx+hy,hxc=hxc,where x,y∈Dm, c∈D.Definition 7.
(collision problem Col(h, Dx)). Given a function h∈HD,Dx,m, find two distinct vectors z0, z1∈Dx such that hz0=hz1.
The following lemma shows that whenDx is some limited domain (e.g., a set of small norm polynomials), solving the Colh,Dx problem is as hard as solving SVPγ in the worst case on the lattice corresponding to the ideal inDx.Lemma 1.
(see [29]).Let n be any power of 2, ringD=Zqx/xn+1, and define the setDx=g∈D:g∞≤d, where d is an integer.HD,Dx,mis a family of hash functions as inDefinition 6such thatm>logq/log2dandq≥4dmn1.5logn. For anyh∈HD,Dx,m, if there exists a polynomial-time algorithm that solvesColh,Dxwith some non-negligible probability, then there exists a polynomial-time algorithm that can solveSVPγover ideal lattice, whereγ=16dmnlog2n.
In addition, we recall the following boundary Lemma to justify the security of the proposed scheme.Lemma 2.
(Lemma 2.11 in [47] applied to our setting).Leta←Ds, c be the response returned by the random oracleH (i.e.,c←Dc), then(8)Prac∞≤nlog2n≥1−4ne−log2n/8=1−n−ω1.


### 2.5. Statistical Distance and Probabilistic Lemma

The difference between two probability distributions can be measured by the statistical distance, and in the security proof of the proposed RS scheme, we complete the proof of anonymity by using it.Definition 8.
(statistical distance). For random variablesX0 and X1 that are defined on a countable set S, if the set S is discrete, then the statistical distance between X0 and X1 is described as(9)ΔX0,X1=12∑x∈SPrX0=x−PrX1=x.
If the random variablesX0 and X1 satisfy ΔX0,X1≤n−ω1, then X0 and X1 are statistically close. Regarding statistical distances, there are the following common properties:(1)
ΔX0,X1≥0;(2)
ΔX0,X1=ΔX1,X0.
In addition, to prove the convergence of our algorithms, the following probabilistic lemma will be used:Lemma 3.
(Corollary 6.2 in [47]).For anys∈Dsm,(10)Prc←Dc,u←Dymsc+u∈Dzm=1e−o1.


## 2.1. Notations

The symbolN represents the abbreviation of the set 1,2,…,N. Let R be the set of real numbers, R+ be the set of positive real numbers, and Z be the set of integers. For a finite set S, the symbol y←S denotes a random uniform sampling from S. The upper-case letter X is the random variable denoting a signature, and X←F denotes X as the output of the signature algorithm F. Vectors and matrices are denoted by lower-case e.g.,x and upper-case e.g.,X letters in italic & bold, respectively. In this work, we construct a cryptographic scheme on ring D=Zqx/xn+1, where xn+1 is an irreducible polynomial, and all logarithms we use are base 2. Zq is the set of integers modulo q, elements in Zq are denoted by integers selected from the interval −q−1/2,q−1/2, and then the elements in D are represented by n−1 degree polynomials whose coefficients are taken from Zq. For a=∑ifixi∈D, the common norms of a are given as follow:(1)l1:a1=∑ifi,l2:a2=∑ifi21/2,l∞:a∞=maxifi.For a polynomial vectora=a1,a2,…,am, where a1,a2,…,am∈D,m is a positive integer, and the infinite norm with respect to a is defined as follows:(2)a∞=maxiai∞.Additionally, we will use the following notations:(3)Dc=g∈D:g∞≤1,Ds=g∈D:g∞≤nlogn,Dx=g∈D:g∞≤mn1.5logn+nlog2n,Dy=g∈D:g∞≤mn1.5logn,Dz=g∈D:g∞≤mn1.5logn−nlog2n.The complexity of algorithms is measured using the standard asymptotic notationsω,O:(4)fn=ωgniflimn⟶∞fngn=∞,fn=Ogniflimn⟶∞fngn≠∞.Use the symbolO˜ to suppress poly-logarithmic factors, and for example, for any constant c and c′, fn=Onclogc′n, we have fn=O˜nc.


## 2.2. Lattice and Ideal Lattice

Micciancio [46] first proposed the concept of cyclic lattice, which to a certain extent eliminated the drawbacks of big key size and operational inefficiency of cryptographic schemes on Euclidean lattice. Lyubashevsky and Micciancio [45] first proposed the definition of an ideal lattice, which is a lattice with a special algebraic structure and is a generalization of the cyclic lattice. In general, a Euclidean lattice is a subgroup of a group, and an ideal lattice is an ideal of a ring.Definition 1.
(lattice). Supposing matrixB is composed of a set of linearly independent vectors b1,b2,…,bm∈Zn , then the integer lattice generated by B is defined as:(5)LO=Bx=∑xibi:x∈Zm,b1,b2,…,bm form a set of bases over LB. In short, LB is a discrete additive subgroup in the n-dimensional real space Rn.Definition 2.
(q-ary lattice). Given a prime q, positive integers m, n, for any matrix A∈Zqn×m, the integer lattice, that is, m-dimensional full-rank is described as follows:(6)Λ⊥A=u∈Zms.t.Au=0modq.Definition 3.
(ideal lattice). Letf be a monic irreducible polynomial of degree n, the ideal I⊆Zx/f, then an integer lattice LB⊆Zn such that LB=gmodf:g∈I is called an ideal lattice.


## 2.3. Hardness Assumption

Definition 4.
(R-SISq,m,β problem). Given a randomly chosen vector a∈Dm, find the vector x∈Dm such that aT⋅x=0 satisfying 0<x2≤β, where q, m are positive integers, β∈R+.Definition 5.
(SVPγ). Given a lattice LB and an approximation factor γ≥1, find a nonzero vector v on lattice such that v∞≤γu∞ holds for any vector u∈LB.


## 2.4. Collision-Resistant Hash Functions and Boundingacmodxn+1∞

Lyubashevsky and Micciancio [45] defined a family of collision-resistant hash functions on ideal lattice, which are efficient functions based on the hardness of worst-case lattice problems, and showed that finding collisions for h∈HD,Dx,m is at least as hard as solving SVPγ, where γ=O˜n2.Definition 6.
(family of hash functions). For any integerm and set Dx, the family of hash functions HD,Dx,m=ha:a∈Dm, where a hash function ha:Dxm⟶D. On input polynomial vectors b=b1,b2,…,bm∈Dxm, then hab=a⋅b=a1b1+a2b2+⋯+ambm. There are two homomorphic properties about h∈HD,Dx,m as follows:(7)hx+y=hx+hy,hxc=hxc,where x,y∈Dm, c∈D.Definition 7.
(collision problem Col(h, Dx)). Given a function h∈HD,Dx,m, find two distinct vectors z0, z1∈Dx such that hz0=hz1.
The following lemma shows that whenDx is some limited domain (e.g., a set of small norm polynomials), solving the Colh,Dx problem is as hard as solving SVPγ in the worst case on the lattice corresponding to the ideal inDx.Lemma 1.
(see [29]).Let n be any power of 2, ringD=Zqx/xn+1, and define the setDx=g∈D:g∞≤d, where d is an integer.HD,Dx,mis a family of hash functions as inDefinition 6such thatm>logq/log2dandq≥4dmn1.5logn. For anyh∈HD,Dx,m, if there exists a polynomial-time algorithm that solvesColh,Dxwith some non-negligible probability, then there exists a polynomial-time algorithm that can solveSVPγover ideal lattice, whereγ=16dmnlog2n.
In addition, we recall the following boundary Lemma to justify the security of the proposed scheme.Lemma 2.
(Lemma 2.11 in [47] applied to our setting).Leta←Ds, c be the response returned by the random oracleH (i.e.,c←Dc), then(8)Prac∞≤nlog2n≥1−4ne−log2n/8=1−n−ω1.


## 2.5. Statistical Distance and Probabilistic Lemma

The difference between two probability distributions can be measured by the statistical distance, and in the security proof of the proposed RS scheme, we complete the proof of anonymity by using it.Definition 8.
(statistical distance). For random variablesX0 and X1 that are defined on a countable set S, if the set S is discrete, then the statistical distance between X0 and X1 is described as(9)ΔX0,X1=12∑x∈SPrX0=x−PrX1=x.
If the random variablesX0 and X1 satisfy ΔX0,X1≤n−ω1, then X0 and X1 are statistically close. Regarding statistical distances, there are the following common properties:(1)
ΔX0,X1≥0;(2)
ΔX0,X1=ΔX1,X0.
In addition, to prove the convergence of our algorithms, the following probabilistic lemma will be used:Lemma 3.
(Corollary 6.2 in [47]).For anys∈Dsm,(10)Prc←Dc,u←Dymsc+u∈Dzm=1e−o1.


## 3. Definition of RS and Security Model

### 3.1. Definition of RS

Suppose there existN members in the ring and each member Uii∈N has a pair of keys, i.e., public key pki and private key ski, a RS scheme can be composed of four polynomial-time algorithms:(1)
Setup1λ: Taking a security parameter λ as input, it outputs the public parameters pp.(2)
KeyGenpp: Taking the public parameters pp as input, it generates a pair of keys pk,sk, where pk and sk denote the public and private keys, respectively.(3)
Signpp,Lpk,μ,skπ: On input public parameters pp, ring Lpk, message μ and the private key skπ of the signer Uπ (require that its corresponding public key pkπ∈Lpk), it outputs an RS sig of Uπ on the message μ under ring Lpk.(4)
Verifypp,Lpk,μ,sig: On input public parameter pp, ring Lpk, message μ and RS sig, if sig satisfies the verification conditions, it outputs 1; otherwise, it outputs 0.


### 3.2. Security Model

For the above algorithms, an RS scheme is called to be secure if it satisfies the following definitions: correctness, anonymity, and unforgeability.Definition 9.
(correctness). If the signer signs honestly, i.e., according to the algorithms in Section3.1, the Verify algorithm will always output 1 with overwhelming probability, that is, equality (11) holds.(11)PrVerifypp,Lpk,μ,sig=1pp←Setup1λpkπ,skπ←KeyGenpppkπ∈Lpksig←Signpp,Lpk,μ,skπ=1−neglλ.
Bender et al. [11] proposed the security definitions of RS under different security degrees, among which the highest degree in terms of anonymity is anonymity-FKE. Based on anonymity-FKE, Aguilar Melchor et al. [41] proposed a stronger definition, namely UA-CSA. In this work, the security proof of anonymity is based on the security model of UA-CSA.
Let’s define a game between adversaryA and challenger S Under UA-CSA since all secrets are known, the adversary can effectively simulate the signature and corrupt oracles, so these two oracles are no longer provided in the game and the procedure in which S generates pp and pk,sk is not required, since they will be generated by the adversary instead. The game is as follows:(i)
Supposel is the upper bound of ring member size in the system, the adversary submits to a set of public parameters pp, ring Lpk=pk1,pk2,…,pkN, two private keys ski0,ski1, message μ, where N, i0,i1∈l.(ii)
S randomly selects b←0,1, invokes Signpp,Lpk,μ,skib to generate the signature sigib, and returns sigib to A.(iii)
AdversaryA outputs a bit b′, and if b′=b, then A wins the game.
The advantage of winning the game is denoted by,(12)AdvAanon=Prb′=b−12.Definition 10.
(anonymity). An RS scheme satisfies UA-CSA ifAdvAanon is negligible for any polynomial-time adversary A.
Bender et al. [11] consider two cases when defining the strongest unforgeability EU-IC: (1) An adversary can trick some honest user into using the public keys that are adversarially generated to generate a signature. (2) The adversary can adaptively corrupt some ring members and obtain their keys. The strongest EU-IC with respect to RS is depicted by the game between adversary A and challenger A′ as follows:(i)
Setup phase: Given security parameterλ, A′ runs the KeyGen algorithm to generate the user’s public/private key pairs, and sends public parameters pp and the maximum set of user’s public keys S=pkii∈l to adversary A.(ii)
Query phase:A is allowed to make adaptive queries to the signature oracle SO and the corrupt oracle CO.(a)
Signing query:A submits to A′ the set of user’s public keys Lpk, message μ and π∈l, where π is an index such that pkπ∈Lpk. On receiving π,μ,Lpk, A′ invokes the Sign algorithm to generate sig and send it to A.(b)
Corruption query:A submits ii∈l to access corrupt oracle CO, then A′ returns the relevant private key ski to A.(iii)
Forgery phase:A outputs μ∗,Lpk∗,sig∗, and we call A gets the triumph if the below conditions are satisfied:(a)
Verifypp,Lpk∗,μ∗,sig∗=1;(b)
A never queried for the signature on ∗,μ∗,Lpk∗;(c)
Lpk∗⊆S\C, where C is the set of corrupted users.
The advantage ofA winning the game is depicted as:(13)AdvAforge=PrAwinsthegame.Definition 11.
(unforgeability). A RS scheme is said to satisfy EU-IC ifAdvAforge is negligible for any polynomial-time adversary A.


## 3.1. Definition of RS

Suppose there existN members in the ring and each member Uii∈N has a pair of keys, i.e., public key pki and private key ski, a RS scheme can be composed of four polynomial-time algorithms:(1)
Setup1λ: Taking a security parameter λ as input, it outputs the public parameters pp.(2)
KeyGenpp: Taking the public parameters pp as input, it generates a pair of keys pk,sk, where pk and sk denote the public and private keys, respectively.(3)
Signpp,Lpk,μ,skπ: On input public parameters pp, ring Lpk, message μ and the private key skπ of the signer Uπ (require that its corresponding public key pkπ∈Lpk), it outputs an RS sig of Uπ on the message μ under ring Lpk.(4)
Verifypp,Lpk,μ,sig: On input public parameter pp, ring Lpk, message μ and RS sig, if sig satisfies the verification conditions, it outputs 1; otherwise, it outputs 0.


## 3.2. Security Model

For the above algorithms, an RS scheme is called to be secure if it satisfies the following definitions: correctness, anonymity, and unforgeability.Definition 9.
(correctness). If the signer signs honestly, i.e., according to the algorithms in Section3.1, the Verify algorithm will always output 1 with overwhelming probability, that is, equality (11) holds.(11)PrVerifypp,Lpk,μ,sig=1pp←Setup1λpkπ,skπ←KeyGenpppkπ∈Lpksig←Signpp,Lpk,μ,skπ=1−neglλ.
Bender et al. [11] proposed the security definitions of RS under different security degrees, among which the highest degree in terms of anonymity is anonymity-FKE. Based on anonymity-FKE, Aguilar Melchor et al. [41] proposed a stronger definition, namely UA-CSA. In this work, the security proof of anonymity is based on the security model of UA-CSA.
Let’s define a game between adversaryA and challenger S Under UA-CSA since all secrets are known, the adversary can effectively simulate the signature and corrupt oracles, so these two oracles are no longer provided in the game and the procedure in which S generates pp and pk,sk is not required, since they will be generated by the adversary instead. The game is as follows:(i)
Supposel is the upper bound of ring member size in the system, the adversary submits to a set of public parameters pp, ring Lpk=pk1,pk2,…,pkN, two private keys ski0,ski1, message μ, where N, i0,i1∈l.(ii)
S randomly selects b←0,1, invokes Signpp,Lpk,μ,skib to generate the signature sigib, and returns sigib to A.(iii)
AdversaryA outputs a bit b′, and if b′=b, then A wins the game.
The advantage of winning the game is denoted by,(12)AdvAanon=Prb′=b−12.Definition 10.
(anonymity). An RS scheme satisfies UA-CSA ifAdvAanon is negligible for any polynomial-time adversary A.
Bender et al. [11] consider two cases when defining the strongest unforgeability EU-IC: (1) An adversary can trick some honest user into using the public keys that are adversarially generated to generate a signature. (2) The adversary can adaptively corrupt some ring members and obtain their keys. The strongest EU-IC with respect to RS is depicted by the game between adversary A and challenger A′ as follows:(i)
Setup phase: Given security parameterλ, A′ runs the KeyGen algorithm to generate the user’s public/private key pairs, and sends public parameters pp and the maximum set of user’s public keys S=pkii∈l to adversary A.(ii)
Query phase:A is allowed to make adaptive queries to the signature oracle SO and the corrupt oracle CO.(a)
Signing query:A submits to A′ the set of user’s public keys Lpk, message μ and π∈l, where π is an index such that pkπ∈Lpk. On receiving π,μ,Lpk, A′ invokes the Sign algorithm to generate sig and send it to A.(b)
Corruption query:A submits ii∈l to access corrupt oracle CO, then A′ returns the relevant private key ski to A.(iii)
Forgery phase:A outputs μ∗,Lpk∗,sig∗, and we call A gets the triumph if the below conditions are satisfied:(a)
Verifypp,Lpk∗,μ∗,sig∗=1;(b)
A never queried for the signature on ∗,μ∗,Lpk∗;(c)
Lpk∗⊆S\C, where C is the set of corrupted users.
The advantage ofA winning the game is depicted as:(13)AdvAforge=PrAwinsthegame.Definition 11.
(unforgeability). A RS scheme is said to satisfy EU-IC ifAdvAforge is negligible for any polynomial-time adversary A.


## 4. Lattice-based RS Scheme without Trapdoors

### 4.1. Construction

(1)
Setup1λ: Given security parameter λ, it outputs the public parameter pp=n,d,q,m,H,h,Ds,Dc,Dx,Dy,Dz, where integer n>λ and is a power of 2, d=nlogn, prime q≥4mn1.5logn2, integer m>logq/log2d, H:0,1∗⟶Dc is a cryptographic hash function, h is randomly chosen from the family HD,Dx,m, and the other parameters are defined in Section 2.1.(2)
KeyGenpp: Given public parameters pp, it picks r←Dsm, then generates the public key pk=hr and sets the private key sk=r.(3)
Signpp,Lpk,μ,skπ: Given public parameters pp, ring Lpk=pk1,pk2,…,pkN, message μ∈0,1∗ and private key skπ=rπ of member Uπ, it runs as follows:(i)
Picku←Dym, calculate cπmodN+1=HLpk,μ,hu;(ii)
Fori=π+1,…,N,1,…,π−1:(a)
Chooserz,i←Dzm;(b)
Calculateti=hrz,i−cipki, cimodN+1=HLpk,μ,ti.(iii)
Calculaterz,π=u+cπrπ;(iv)
Ifrz,π∉Dzm, then return to step (i);(v)
Output the signaturesig=c1,rz.ii∈N.(4)
Verifypp,Lpk,μ,sig: Given public parameters pp, ring Lpk=pk1,pk2,…,pkN, message μ∈0,1∗ and signature sig=c1,rz.ii∈N, it accepts the signature and outputs 1 only if sig satisfies the below conditions, otherwise it rejects the signature and outputs 0.(i)
Fori∈N, rz,i∈Dzm;(ii)
Fori∈N, calculate ti=hrz,i−cipki, ci+1=HLpk,μ,ti, and determine c1=HLpk,μ,tN=cN+1.


### 4.2. Correctness and Convergence of the Scheme

Theorem 1.
(correctness).The proposed RS scheme satisfies correctness.Proof.
Whensig is a signature generated according to the signature algorithm, then (a) in step (ii) and step (iv) of Sign ensure that rz,ii∈N are elements in Dzm. In addition, we have the following equations:(14)c2=HLpk,μ,t1,wheret1=hrz,1−c1pk1,c3=HLpk,μ,t2,wheret2=hrz,2−c2pk2,⋮cπ=HLpk,μ,tπ−1,wheretπ−1=hrz,π−1−cπ−1pkπ−1,sincerz,π=u+cπrπ∈Dzm,we havecπ+1=HLpk,μ,tπ=HLpk,μ,hrz,π−cπpkπ=HLpk,μ,hu+cπrπ−cπpkπ=HLpk,μ,hu,cπ+2=HLpk,μ,tπ+1,wheretπ+1=hrz,π+1−cπ+1pkπ+1,cπ+3=HLpk,μ,tπ+2,wheretπ+2=hrz,π+2−cπ+2pkπ+2,⋮c1=cN+1=HLpk,μ,tN,wheretN=hrz,N−cNpkN.
To sum up, the polynomial sequencec1,c2,…,cN in the verification process is equal to that in the signature process, so it must pass the verification of the Verify algorithm, and the proposed scheme is correct.Theorem 2.
(convergence).Under the parameter settings of algorithm Setup, the expected runtime of the proposed scheme isO˜n, and algorithm Sign is expected to repeat no more than three times.Proof.
The proposed RS scheme is made up of four algorithms:Setup,KeyGen,Sign and Verify The Setup algorithm selects a hash function h∈HD,Dx,m (i.e., pick mn random numbers from −q−1/2,−q−1/2+1,…,q−1/2 ), the time for the step is negligible. The step of generating a single user’s private/public keys in KeyGen is to randomly select a vector r←Dsm, which simply involves randomly selecting mn numbers from the set −nlogn,…,nlogn, and then calculating pk=hr, which takes O˜n time according to Lemma 2.16 from [47]. The Sign algorithm is to randomly selects a vector u←Dym and N−1 vectors rz,i←Dzm, then calculate small polynomial multiplication cipki and hash function h∈HD,Dx,mN times, and access random oracles N times. The time of Sign algorithm running once is O˜n from [47], but if rz,π∉Dzm, then the operations of Sign need to be repeated again. Lemma 3 states that for any r←Dsm, Pru←Dym,c←Dsu+cr∈Dzm=1/e−o1. Therefore, we will iterate Sign no more than three times and the runtime of Sign is also O˜n. Finally, the Verify algorithm needs to calculate small polynomial multiplication cipki and function h∈HD,Dx,mN times, and access random oracles N times, thus the running time is also O˜n.


## 4.1. Construction

(1)
Setup1λ: Given security parameter λ, it outputs the public parameter pp=n,d,q,m,H,h,Ds,Dc,Dx,Dy,Dz, where integer n>λ and is a power of 2, d=nlogn, prime q≥4mn1.5logn2, integer m>logq/log2d, H:0,1∗⟶Dc is a cryptographic hash function, h is randomly chosen from the family HD,Dx,m, and the other parameters are defined in Section 2.1.(2)
KeyGenpp: Given public parameters pp, it picks r←Dsm, then generates the public key pk=hr and sets the private key sk=r.(3)
Signpp,Lpk,μ,skπ: Given public parameters pp, ring Lpk=pk1,pk2,…,pkN, message μ∈0,1∗ and private key skπ=rπ of member Uπ, it runs as follows:(i)
Picku←Dym, calculate cπmodN+1=HLpk,μ,hu;(ii)
Fori=π+1,…,N,1,…,π−1:(a)
Chooserz,i←Dzm;(b)
Calculateti=hrz,i−cipki, cimodN+1=HLpk,μ,ti.(iii)
Calculaterz,π=u+cπrπ;(iv)
Ifrz,π∉Dzm, then return to step (i);(v)
Output the signaturesig=c1,rz.ii∈N.(4)
Verifypp,Lpk,μ,sig: Given public parameters pp, ring Lpk=pk1,pk2,…,pkN, message μ∈0,1∗ and signature sig=c1,rz.ii∈N, it accepts the signature and outputs 1 only if sig satisfies the below conditions, otherwise it rejects the signature and outputs 0.(i)
Fori∈N, rz,i∈Dzm;(ii)
Fori∈N, calculate ti=hrz,i−cipki, ci+1=HLpk,μ,ti, and determine c1=HLpk,μ,tN=cN+1.


## 4.2. Correctness and Convergence of the Scheme

Theorem 1.
(correctness).The proposed RS scheme satisfies correctness.Proof.
Whensig is a signature generated according to the signature algorithm, then (a) in step (ii) and step (iv) of Sign ensure that rz,ii∈N are elements in Dzm. In addition, we have the following equations:(14)c2=HLpk,μ,t1,wheret1=hrz,1−c1pk1,c3=HLpk,μ,t2,wheret2=hrz,2−c2pk2,⋮cπ=HLpk,μ,tπ−1,wheretπ−1=hrz,π−1−cπ−1pkπ−1,sincerz,π=u+cπrπ∈Dzm,we havecπ+1=HLpk,μ,tπ=HLpk,μ,hrz,π−cπpkπ=HLpk,μ,hu+cπrπ−cπpkπ=HLpk,μ,hu,cπ+2=HLpk,μ,tπ+1,wheretπ+1=hrz,π+1−cπ+1pkπ+1,cπ+3=HLpk,μ,tπ+2,wheretπ+2=hrz,π+2−cπ+2pkπ+2,⋮c1=cN+1=HLpk,μ,tN,wheretN=hrz,N−cNpkN.
To sum up, the polynomial sequencec1,c2,…,cN in the verification process is equal to that in the signature process, so it must pass the verification of the Verify algorithm, and the proposed scheme is correct.Theorem 2.
(convergence).Under the parameter settings of algorithm Setup, the expected runtime of the proposed scheme isO˜n, and algorithm Sign is expected to repeat no more than three times.Proof.
The proposed RS scheme is made up of four algorithms:Setup,KeyGen,Sign and Verify The Setup algorithm selects a hash function h∈HD,Dx,m (i.e., pick mn random numbers from −q−1/2,−q−1/2+1,…,q−1/2 ), the time for the step is negligible. The step of generating a single user’s private/public keys in KeyGen is to randomly select a vector r←Dsm, which simply involves randomly selecting mn numbers from the set −nlogn,…,nlogn, and then calculating pk=hr, which takes O˜n time according to Lemma 2.16 from [47]. The Sign algorithm is to randomly selects a vector u←Dym and N−1 vectors rz,i←Dzm, then calculate small polynomial multiplication cipki and hash function h∈HD,Dx,mN times, and access random oracles N times. The time of Sign algorithm running once is O˜n from [47], but if rz,π∉Dzm, then the operations of Sign need to be repeated again. Lemma 3 states that for any r←Dsm, Pru←Dym,c←Dsu+cr∈Dzm=1/e−o1. Therefore, we will iterate Sign no more than three times and the runtime of Sign is also O˜n. Finally, the Verify algorithm needs to calculate small polynomial multiplication cipki and function h∈HD,Dx,mN times, and access random oracles N times, thus the running time is also O˜n.


## 5. Security

### 5.1. Anonymity

Before proving the anonymity of the proposed scheme, we first give and prove the following lemma, which shows that for an adversary who has the ability to distinguish two ring signatures based on adversarially-chosen private keys and the correspondingcπ associated with the private keys, the statistical distance between the following two sets of random variables Y0 and Y1 is negligible.Define two sets of random variablesY0=αi∈Dzm;i∈N,β and Y1=αi∈Dzm;i∈N,β that are obtained from the Sign algorithm with input pp,Lpk,μ,ski0 and pp,Lpk,μ,ski1, where the first N components of Yb represent the first N outputs rz,ii∈N of sigib, and the (N+1)-th component of Yb represents cπ corresponding to sigib, b←0,1. In addition, we use Ybi to represent the i-th component of Yb, i∈N+1, e.g., Y0N+1 represents cπ.Lemma 4.
IfY0andY1are random variables obtained from two legitimate signatures, and these two legitimate signatures are generated by private keysski0,ski1which are adversarially-chosen, we have(15)ΔY0,Y1=n−ω1.Proof.
First define a setDcski0,ski1=d∈Dc:ski0d∞,ski1d∞≤nlog2n. According to Lemma 2, it is concluded that almost all elements of Dc are in Dcski0,ski1. Even if the private keys ski0,ski1∈Ds, n≥λ are chosen by the adversary, Lemma 2 will also guarantee that Dcski0,ski1/Dc=1−n−ω1, where n−ω1 is a negligible function. Then divide the statistical distance ΔY0,Y1 into two parts, we have formulas (16) and (17).
Next we will discussΔY0,Y1 in two steps, first to prove that formula (16) is negligible (Step 1), and then to prove that formula (17) is equal to zero (Step 2).(16)ΔY0,Y1=12∑αi∈Dsm;i∈N,βPrY0=αi;i∈N,β−PrY1=αi;i∈N,β,=12∑αi∈Dsm;i∈N,β∉Dcski0,ski1PrY0=αi;i∈N,β−PrY1=αi;i∈N,β,(17)+12∑αi∈Dsm;i∈N,β∈Dcski0,ski1PrY0=αi;i∈N,β−PrY1=αi;i∈N,β.Step 1.
Considering the case ofβ∉Dcski0,ski1, generally, since(18)17≤12∑αi∈Dsm;i∈N,β∉Dcski0,ski1PrY0=αi;i∈N,β≤12∑β∉Dcski0,ski1PrY0N+1=β≤∑β∉Dcski0,ski1PrY0N+1=β,and since for any b∈0,1, the variable YbN+1 is calculated by the hash function HLpk,μ,tπ−1, where tπ−1=hrz,π−1−cπ−1pkπ−1, thus β∈Dc and the probability that YbN+1 is equal to the given value β is 1/Dc. Note that even hash function h∈HD,Dx,m is adversarially chosen, it does not affect the probability that Y0N+1 is equal to a given β. Further, for each β∉Dcski0,ski1, PrY0N+1=β=1/Dc, and since almost all elements of Dc are in Dcski0,ski1 from Lemma 2, it is evident that the probability of β∉Dcski0,ski1 is negligible. And then we get(19)17≤∑β∉Dcski0,ski11Dc=Dc−Dcski0,ski1Dc=1−Dcski0,ski1Dc=n−ω1.Step 2.
To prove that the value of formula (17) is zero, it is only necessary to prove that each term in formula (17) is zero. Since the last component YbN+1 of Yb is derived from a random oracle H, the probability that Y0N+1 and Y1N+1 are equal to a given value β is the same. Then it is only necessary to prove that the following equation about conditional probabilities holds:(20)PrY0i;i∈N=αi;i∈NY0N+1=β=PrY1i;i∈N=αi;i∈NY1N+1=β.
For anyb∈0,1, Ybi=αi∈Dzm if i∈N\ib, thus the probability that Ybi is equal to a given value is 1/Dzm; if i=ib,(21)PrYbib=αib=Prub+skibβ=αib=Prub=αib−skibβ.
Sinceβ∈Dcski0,ski1, αib∈Dzm, we have ski0β∞, ski1β∞≤nlog2n, αib∞≤mn1.5logn−nlog2n, then αi0−ski0β∞=αi1−ski1β∞≤mn1.5logn. Thus, the values of both αi0−ski0β and αi1−ski1β belong to the set Dym. And since u0,u1←Dym, Pru0=αi0−ski0β=Pru1=αi1−skπ1β=1/Dym.
In summary, for anyb∈0,1,(22)PrYbi=αiYbN+1=β=1Dzm,i∈N\ib,1Dym,i=ib.
Therefore, it can be proved that equation (20) holds, i.e., the proof of the lemma is completed.
Suppose that in the game of anonymity in Section3.2, pp are adversarially chosen according to the Setup algorithm, pki0 and pki1 are adversarially generated according to the KeyGen algorithm, message μ and ring Lpk are also chosen by adversary. The challenger chooses b←0,1 and invokes Signpp,Lpk,μ,skb to generate a signature, and give it to the adversary. Define the random variable Xb,pp,skib,μ,Lpk to represent the signature generated by the challenger, and the following theorem shows that the statistical distance between X0,pp,ski0,μ,Lpk and X1,pp,ski1,μ,Lpk is negligible.Theorem 3.
(anonymity).The proposed scheme satisfies UA-CSA, i.e., for the adversary in Definition 10,Xb,pp,skib,μ,Lpk←Signpp,Lpk,μ,skib,b∈0,1, we have(23)ΔX0,pp,ski0,μ,Lpk,X1,pp,ski1,μ,Lpk=n−ω1.Proof.
RegardingXb,pp,skib,μ,Lpk, it is known from the signing process, rz,i←Dzm if i≠ib; rz,i=u+ciri if i=ib. By Lemma 3 and Theorem 2, we know that rz,i is indistinguishable from a randomly selected vector in Dzm. And since the first component c1 in Xb,pp,skib,μ,Lpk is from a random oracle, the statistical distance ΔX0,pp,ski0,μ,Lpk,X1,pp,ski1,μ,Lpk=n−ω1 for an ordinary adversary A. However, for an UA-CSA adversary, obviously, such an analysis is not rigorous enough. The following will focus on the verification process, whether the adversary can distinguish the two signatures based on adversarially-chosen private keys and cπ associated with the private keys.
Since the first componentc1 of Xb,pp,skib,μ,Lpk is obtained by accessing a random oracle, and it is not directly related to the associated private key, thus the discussion with respect to c1 is not necessary. We only need to prove that for an UA-CSA adversary, the statistical distance between the defined Y0,Y1 is negligible. By Lemma 4 it is known that ΔY0,Y1=n−ω1, thus for an UA-CSA adversary, the probability of winning the anonymity game is also negligible. That completes the proof.


### 5.2. Unforgeability

Before proving unforgeability, the following lemma is first given and proved.Lemma 5.
Letr,r′←Ds,v,v′←Dz,c,c′←Dcandc≠c′, ifv−cr=v′−c′r,r≠r′, then the following inequality holds:(24)v−cr′≠v′−c′r′.Proof.
Assume that bothv−cr=v′−c′r and v−cr′=v′−c′r′ hold. By subtracting the two equations, we have r′−rc′−c=0. Since the equation holds in ring Zqx/xn+1, it does not directly deduce that r′=r or c′=c holds. Due to r′∞,r∞≤nlogn, c′∞,c∞≤1, then the absolute values of the coefficients of r′−r and c′−c are no more than 2nlogn and 2, respectively. When r′−r is multiplied by c′−c in ring Zx/xn+1, the absolute value of the coefficients of r′−rc′−c is no more than 4n1.5logn. Since q≫4n1.5logn, if r′−rc′−c=0 holds in ring Zqx/xn+1, then it must also hold in ring Zx/xn+1. And since c≠c′, then it must have r′=r, which is contradictory to the assumption, thus the lemma is proved.Theorem 4.
(unforgeability).Under the random oracle model, if there exists a polynomial-time adversaryAwho can validly forge a RS signature about the proposed scheme with probabilityε, then for a random-chosenh∈HD,Dx,m, there is a polynomial-time algorithmA′that can obtain a solution toColh,Dxwith probability at leastε2/2ψ+3Nζ, where N,ζandψare the number of ring members, the maximum times thatAaccessesSOand directly accessesHO, respectively.Proof.
Suppose there exists an EU-IC adversaryA who can validly forge a signature against the proposed scheme with non-negligible probability ε, then there exists a challenger A′ who can solve Colh,Dx with non-negligible probability ε′.
Suppose the number of maximum ring members in the system isl=lλ, and given a hash function family HD,Dx,m, A′ obtains an instance (h) from the Colh,Dx oracle as an input. A′ maintains two lists L1 and L2, which are initialized to be null. For i∈l, A′ honestly runs the Keygen algorithm to generate the key pair pki,ski, and stores the tuple i,pki,ski in list L1. A′ gives the public key set S=pk1,pk2,…,pkl to A, and then A′ simulates oracles and responds to the queries from A in the following manner:
Hash queryHO: A submits a set of ring members Lpk=pk1,pk2,…,pkN⊂S, message μ∈0,1∗ and ti∈D, A′ inquires the list L2, and if the tuple Lpk,μ,ti,ci+1 exists, A′ returns ci+1 to A. Otherwise, A′ randomly selects ci+1∈Dc and returns it to A, and adds Lpk,μ,ti,ci+1 to the list L2.
Signing querySO: A submits an index π, a message μ∈0,1∗ and a set of ring members Lpk=pk1,pk2,…,pkN (which may contain some public keys generated by A in an arbitrary way). Note that since A′ knows the private keys of all members in set S, and in general, A will not query signatures about a user outside S, which is meaningless. A′ responds to this query by honestly running the Sign algorithm.
Corruption queryCO: A can make corruption query about any user Ui (i∈l). If A makes a query on i,pki, A′ first obtains the tuple i,pki,ski by looking for the list L1, and then returns ski to A.
Forgery phase: Suppose that after finishing the above queries,A outputs a valid forgery μ∗,Lpk∗,sig∗ with non-negligible probability, ε and A did not ask for any signature on ∗,μ∗,Lpk∗, where Lpk∗⊆S\C and C is the set of corrupted users.
Analysis. Define p as the maximum times HO is queried during A’s attack. By Theorem 2, we know that it takes at most 3NHO queries to produce a RS, and since A can make SO queries at most ζ times, the value of p is at most ψ+3Nζ. Suppose that sig∗=c1∗,rz,i∗i∈N can pass the verification of Verify, then in general, it can be assumed that for some j, we have HLpk∗,μ∗,hrz,j∗−cj∗pkj∗=cj+1∗.
IfA did not query HO on Lpk∗,μ∗,hrz,j∗−cj∗pkj∗, then the probability of producing cj+1∗ such that HLpk∗,μ∗,hrz,j∗−cj∗pkj∗=cj+1∗ is only 1/Dc. Hence, the probability that cj+1∗∈s1,s2,…,sp is 1−1/Dc, where s1,s2,…,sp←Dc is the sequence of return values from HO. Further, the probability that A succeeds in a forgery and cj+1∗∈s1,s2,…,sp is at least ε−1/Dc. Suppose cj+1∗=sj, then there are two cases: (1) sj is a response to SO query (Case 1); (2) sj is a response to HO query (Case 2). We first analyze Case 1.Case 1.
Supposecj+1∗ appears during signing query, and suppose that the corresponding response A obtains is the signature sig=c1,rz,ii∈N (i.e., cj+1∗=HLpk,μ,hrz,j−cjpkj). Then compare the signature forged by A with the legitimate signature sig=c1,rz,ii∈N, we have(25)cj+1∗=HLpk∗,μ∗,hrz,j∗−cj∗pkj∗=HLpk,μ,hrz,j−cjpkj.
Then eitherLpk∗≠Lpk or μ∗≠μ (or rz,j∗≠rz,j), since if all three equations hold, this means the adversary simply outputs a signature that has already been asked. If at least one of Lpk∗≠Lpk and μ∗≠μ holds, it implies that a collision has occurred in H. Hence there is Lpk∗=Lpk, μ∗=μ and rz,j∗≠rz,j with overwhelming probability, that is, HLpk∗,μ∗,hrz,j∗−cj∗pkj∗=cj+1∗=HLpk∗,μ∗,hrz,j−cj∗pkj∗. Therefore either hrz,j∗−cj∗pkj∗≠hrz,j−cj∗pkj∗, which implies there is a collision in H, or hrz,j∗−cj∗pkj∗=hrz,j−cj∗pkj∗, which implies there is hrz,j∗=hrz,j. Then we find a collision for h, and since rz,j,rz,j∗∈Dzm⊂Dxm, we find a solution to Colh,Dx. Note that after HO is queried p times, the probability that a collision happens in H is no more than p/Dc, therefore, the probability of A outputting a forgery as a solution to Colh,Dx is at least,(26)ε−pDc.Case 2.
The next is to consider the case thatsj is obtained by A calling HO. In this scenario, suppose that A′ runs A with some randomness and A′ obtains a valid forgery sig∗=c1∗,rz,i∗i∈N of μ∗. Suppose that s1,…,sp←Dc is the sequence of response values from HO during this forgery. Then generate fresh random elements sj′,…,sp′←Dc, and A′ runs A with the same randomness and responds to A’sHO query with s1,…,sj−1,sj′,…,sp′, by forking lemma from [48], A′ will obtain another forged signature sig′=c1′,rz,ii∈N on message μ∗ and sj≠sj′ with probability at leastε−1/Dcε−1/Dc/ψ+3Nζ−1/Dc. Since the input of HO query is the same in both forgeries, we have hrz,j∗−cj∗pkj∗=hrz,j′−cj′pkj∗. By the homomorphic properties of h in Definition 6, it follows that hrz,j∗−cj∗rj∗=hrz,j′−cj′rj∗. If rz,j∗−cj∗rj∗≠rz,j′−cj′rj∗ and rz,j∗−cj∗rj∗,rz,j′−cj′rj∗∈Dxm, then A′ finds a collision for h.
Next, we analyze the probability ofrz,j∗−cj∗rj∗≠rz,j′−cj′rj∗. By Lemma 5.2 in [47], we know that there is a distinct private key rj′ such that pkj=hrj′=hrj∗ with overwhelming probability. And by Lemma 5, if the private key rj∗ satisfies rz,j∗−cj∗rj∗=rz,j′−cj′rj∗, then for another private key rj′, we have rz,j∗−cj∗rj′≠rz,j′−cj′rj′. By Theorem 6.5 from [47], it is statistically impossible to distinguish which one of rj′ and rj∗ is used by the signer, and thus the probability of rz,j∗−cj∗rj∗≠rz,j′−cj′rj∗ is at least 1/2−n−ω1. And for any response from HO, si∈Dc, then by Lemma 2, we have rz,j∗−cj∗rj∗∞, rz,j′−cj′rj∗∞≤mn1.5logn, i.e., rz,j∗−cj∗rj∗, rz,j′−cj′rj∗∈Dym⊂Dxm, which implies that A′ finds a solution to Colh,Dx.
From the above analysis, we know that the probability ofA′ breaking Colh,Dx via A calling SO is at least ε−p/Dc, while the probability of A′ breaking Colh,Dx via A calling HO is at least,(27)12−n−ω1ε−1Dcε−1/Dcψ+3Nζ−1Dc.
By comparing formulas (26) and (27), we have the inequality (26) > (27). Thus, the probability of A′ running A to solve Colh,Dx successfully is,(28)ε′≥12−n−ω1ε−1Dcε−1/Dcψ+3Nζ−1Dc.


## 5.1. Anonymity

Before proving the anonymity of the proposed scheme, we first give and prove the following lemma, which shows that for an adversary who has the ability to distinguish two ring signatures based on adversarially-chosen private keys and the correspondingcπ associated with the private keys, the statistical distance between the following two sets of random variables Y0 and Y1 is negligible.Define two sets of random variablesY0=αi∈Dzm;i∈N,β and Y1=αi∈Dzm;i∈N,β that are obtained from the Sign algorithm with input pp,Lpk,μ,ski0 and pp,Lpk,μ,ski1, where the first N components of Yb represent the first N outputs rz,ii∈N of sigib, and the (N+1)-th component of Yb represents cπ corresponding to sigib, b←0,1. In addition, we use Ybi to represent the i-th component of Yb, i∈N+1, e.g., Y0N+1 represents cπ.Lemma 4.
IfY0andY1are random variables obtained from two legitimate signatures, and these two legitimate signatures are generated by private keysski0,ski1which are adversarially-chosen, we have(15)ΔY0,Y1=n−ω1.Proof.
First define a setDcski0,ski1=d∈Dc:ski0d∞,ski1d∞≤nlog2n. According to Lemma 2, it is concluded that almost all elements of Dc are in Dcski0,ski1. Even if the private keys ski0,ski1∈Ds, n≥λ are chosen by the adversary, Lemma 2 will also guarantee that Dcski0,ski1/Dc=1−n−ω1, where n−ω1 is a negligible function. Then divide the statistical distance ΔY0,Y1 into two parts, we have formulas (16) and (17).
Next we will discussΔY0,Y1 in two steps, first to prove that formula (16) is negligible (Step 1), and then to prove that formula (17) is equal to zero (Step 2).(16)ΔY0,Y1=12∑αi∈Dsm;i∈N,βPrY0=αi;i∈N,β−PrY1=αi;i∈N,β,=12∑αi∈Dsm;i∈N,β∉Dcski0,ski1PrY0=αi;i∈N,β−PrY1=αi;i∈N,β,(17)+12∑αi∈Dsm;i∈N,β∈Dcski0,ski1PrY0=αi;i∈N,β−PrY1=αi;i∈N,β.Step 1.
Considering the case ofβ∉Dcski0,ski1, generally, since(18)17≤12∑αi∈Dsm;i∈N,β∉Dcski0,ski1PrY0=αi;i∈N,β≤12∑β∉Dcski0,ski1PrY0N+1=β≤∑β∉Dcski0,ski1PrY0N+1=β,and since for any b∈0,1, the variable YbN+1 is calculated by the hash function HLpk,μ,tπ−1, where tπ−1=hrz,π−1−cπ−1pkπ−1, thus β∈Dc and the probability that YbN+1 is equal to the given value β is 1/Dc. Note that even hash function h∈HD,Dx,m is adversarially chosen, it does not affect the probability that Y0N+1 is equal to a given β. Further, for each β∉Dcski0,ski1, PrY0N+1=β=1/Dc, and since almost all elements of Dc are in Dcski0,ski1 from Lemma 2, it is evident that the probability of β∉Dcski0,ski1 is negligible. And then we get(19)17≤∑β∉Dcski0,ski11Dc=Dc−Dcski0,ski1Dc=1−Dcski0,ski1Dc=n−ω1.Step 2.
To prove that the value of formula (17) is zero, it is only necessary to prove that each term in formula (17) is zero. Since the last component YbN+1 of Yb is derived from a random oracle H, the probability that Y0N+1 and Y1N+1 are equal to a given value β is the same. Then it is only necessary to prove that the following equation about conditional probabilities holds:(20)PrY0i;i∈N=αi;i∈NY0N+1=β=PrY1i;i∈N=αi;i∈NY1N+1=β.
For anyb∈0,1, Ybi=αi∈Dzm if i∈N\ib, thus the probability that Ybi is equal to a given value is 1/Dzm; if i=ib,(21)PrYbib=αib=Prub+skibβ=αib=Prub=αib−skibβ.
Sinceβ∈Dcski0,ski1, αib∈Dzm, we have ski0β∞, ski1β∞≤nlog2n, αib∞≤mn1.5logn−nlog2n, then αi0−ski0β∞=αi1−ski1β∞≤mn1.5logn. Thus, the values of both αi0−ski0β and αi1−ski1β belong to the set Dym. And since u0,u1←Dym, Pru0=αi0−ski0β=Pru1=αi1−skπ1β=1/Dym.
In summary, for anyb∈0,1,(22)PrYbi=αiYbN+1=β=1Dzm,i∈N\ib,1Dym,i=ib.
Therefore, it can be proved that equation (20) holds, i.e., the proof of the lemma is completed.
Suppose that in the game of anonymity in Section3.2, pp are adversarially chosen according to the Setup algorithm, pki0 and pki1 are adversarially generated according to the KeyGen algorithm, message μ and ring Lpk are also chosen by adversary. The challenger chooses b←0,1 and invokes Signpp,Lpk,μ,skb to generate a signature, and give it to the adversary. Define the random variable Xb,pp,skib,μ,Lpk to represent the signature generated by the challenger, and the following theorem shows that the statistical distance between X0,pp,ski0,μ,Lpk and X1,pp,ski1,μ,Lpk is negligible.Theorem 3.
(anonymity).The proposed scheme satisfies UA-CSA, i.e., for the adversary in Definition 10,Xb,pp,skib,μ,Lpk←Signpp,Lpk,μ,skib,b∈0,1, we have(23)ΔX0,pp,ski0,μ,Lpk,X1,pp,ski1,μ,Lpk=n−ω1.Proof.
RegardingXb,pp,skib,μ,Lpk, it is known from the signing process, rz,i←Dzm if i≠ib; rz,i=u+ciri if i=ib. By Lemma 3 and Theorem 2, we know that rz,i is indistinguishable from a randomly selected vector in Dzm. And since the first component c1 in Xb,pp,skib,μ,Lpk is from a random oracle, the statistical distance ΔX0,pp,ski0,μ,Lpk,X1,pp,ski1,μ,Lpk=n−ω1 for an ordinary adversary A. However, for an UA-CSA adversary, obviously, such an analysis is not rigorous enough. The following will focus on the verification process, whether the adversary can distinguish the two signatures based on adversarially-chosen private keys and cπ associated with the private keys.
Since the first componentc1 of Xb,pp,skib,μ,Lpk is obtained by accessing a random oracle, and it is not directly related to the associated private key, thus the discussion with respect to c1 is not necessary. We only need to prove that for an UA-CSA adversary, the statistical distance between the defined Y0,Y1 is negligible. By Lemma 4 it is known that ΔY0,Y1=n−ω1, thus for an UA-CSA adversary, the probability of winning the anonymity game is also negligible. That completes the proof.


## 5.2. Unforgeability

Before proving unforgeability, the following lemma is first given and proved.Lemma 5.
Letr,r′←Ds,v,v′←Dz,c,c′←Dcandc≠c′, ifv−cr=v′−c′r,r≠r′, then the following inequality holds:(24)v−cr′≠v′−c′r′.Proof.
Assume that bothv−cr=v′−c′r and v−cr′=v′−c′r′ hold. By subtracting the two equations, we have r′−rc′−c=0. Since the equation holds in ring Zqx/xn+1, it does not directly deduce that r′=r or c′=c holds. Due to r′∞,r∞≤nlogn, c′∞,c∞≤1, then the absolute values of the coefficients of r′−r and c′−c are no more than 2nlogn and 2, respectively. When r′−r is multiplied by c′−c in ring Zx/xn+1, the absolute value of the coefficients of r′−rc′−c is no more than 4n1.5logn. Since q≫4n1.5logn, if r′−rc′−c=0 holds in ring Zqx/xn+1, then it must also hold in ring Zx/xn+1. And since c≠c′, then it must have r′=r, which is contradictory to the assumption, thus the lemma is proved.Theorem 4.
(unforgeability).Under the random oracle model, if there exists a polynomial-time adversaryAwho can validly forge a RS signature about the proposed scheme with probabilityε, then for a random-chosenh∈HD,Dx,m, there is a polynomial-time algorithmA′that can obtain a solution toColh,Dxwith probability at leastε2/2ψ+3Nζ, where N,ζandψare the number of ring members, the maximum times thatAaccessesSOand directly accessesHO, respectively.Proof.
Suppose there exists an EU-IC adversaryA who can validly forge a signature against the proposed scheme with non-negligible probability ε, then there exists a challenger A′ who can solve Colh,Dx with non-negligible probability ε′.
Suppose the number of maximum ring members in the system isl=lλ, and given a hash function family HD,Dx,m, A′ obtains an instance (h) from the Colh,Dx oracle as an input. A′ maintains two lists L1 and L2, which are initialized to be null. For i∈l, A′ honestly runs the Keygen algorithm to generate the key pair pki,ski, and stores the tuple i,pki,ski in list L1. A′ gives the public key set S=pk1,pk2,…,pkl to A, and then A′ simulates oracles and responds to the queries from A in the following manner:
Hash queryHO: A submits a set of ring members Lpk=pk1,pk2,…,pkN⊂S, message μ∈0,1∗ and ti∈D, A′ inquires the list L2, and if the tuple Lpk,μ,ti,ci+1 exists, A′ returns ci+1 to A. Otherwise, A′ randomly selects ci+1∈Dc and returns it to A, and adds Lpk,μ,ti,ci+1 to the list L2.
Signing querySO: A submits an index π, a message μ∈0,1∗ and a set of ring members Lpk=pk1,pk2,…,pkN (which may contain some public keys generated by A in an arbitrary way). Note that since A′ knows the private keys of all members in set S, and in general, A will not query signatures about a user outside S, which is meaningless. A′ responds to this query by honestly running the Sign algorithm.
Corruption queryCO: A can make corruption query about any user Ui (i∈l). If A makes a query on i,pki, A′ first obtains the tuple i,pki,ski by looking for the list L1, and then returns ski to A.
Forgery phase: Suppose that after finishing the above queries,A outputs a valid forgery μ∗,Lpk∗,sig∗ with non-negligible probability, ε and A did not ask for any signature on ∗,μ∗,Lpk∗, where Lpk∗⊆S\C and C is the set of corrupted users.
Analysis. Define p as the maximum times HO is queried during A’s attack. By Theorem 2, we know that it takes at most 3NHO queries to produce a RS, and since A can make SO queries at most ζ times, the value of p is at most ψ+3Nζ. Suppose that sig∗=c1∗,rz,i∗i∈N can pass the verification of Verify, then in general, it can be assumed that for some j, we have HLpk∗,μ∗,hrz,j∗−cj∗pkj∗=cj+1∗.
IfA did not query HO on Lpk∗,μ∗,hrz,j∗−cj∗pkj∗, then the probability of producing cj+1∗ such that HLpk∗,μ∗,hrz,j∗−cj∗pkj∗=cj+1∗ is only 1/Dc. Hence, the probability that cj+1∗∈s1,s2,…,sp is 1−1/Dc, where s1,s2,…,sp←Dc is the sequence of return values from HO. Further, the probability that A succeeds in a forgery and cj+1∗∈s1,s2,…,sp is at least ε−1/Dc. Suppose cj+1∗=sj, then there are two cases: (1) sj is a response to SO query (Case 1); (2) sj is a response to HO query (Case 2). We first analyze Case 1.Case 1.
Supposecj+1∗ appears during signing query, and suppose that the corresponding response A obtains is the signature sig=c1,rz,ii∈N (i.e., cj+1∗=HLpk,μ,hrz,j−cjpkj). Then compare the signature forged by A with the legitimate signature sig=c1,rz,ii∈N, we have(25)cj+1∗=HLpk∗,μ∗,hrz,j∗−cj∗pkj∗=HLpk,μ,hrz,j−cjpkj.
Then eitherLpk∗≠Lpk or μ∗≠μ (or rz,j∗≠rz,j), since if all three equations hold, this means the adversary simply outputs a signature that has already been asked. If at least one of Lpk∗≠Lpk and μ∗≠μ holds, it implies that a collision has occurred in H. Hence there is Lpk∗=Lpk, μ∗=μ and rz,j∗≠rz,j with overwhelming probability, that is, HLpk∗,μ∗,hrz,j∗−cj∗pkj∗=cj+1∗=HLpk∗,μ∗,hrz,j−cj∗pkj∗. Therefore either hrz,j∗−cj∗pkj∗≠hrz,j−cj∗pkj∗, which implies there is a collision in H, or hrz,j∗−cj∗pkj∗=hrz,j−cj∗pkj∗, which implies there is hrz,j∗=hrz,j. Then we find a collision for h, and since rz,j,rz,j∗∈Dzm⊂Dxm, we find a solution to Colh,Dx. Note that after HO is queried p times, the probability that a collision happens in H is no more than p/Dc, therefore, the probability of A outputting a forgery as a solution to Colh,Dx is at least,(26)ε−pDc.Case 2.
The next is to consider the case thatsj is obtained by A calling HO. In this scenario, suppose that A′ runs A with some randomness and A′ obtains a valid forgery sig∗=c1∗,rz,i∗i∈N of μ∗. Suppose that s1,…,sp←Dc is the sequence of response values from HO during this forgery. Then generate fresh random elements sj′,…,sp′←Dc, and A′ runs A with the same randomness and responds to A’sHO query with s1,…,sj−1,sj′,…,sp′, by forking lemma from [48], A′ will obtain another forged signature sig′=c1′,rz,ii∈N on message μ∗ and sj≠sj′ with probability at leastε−1/Dcε−1/Dc/ψ+3Nζ−1/Dc. Since the input of HO query is the same in both forgeries, we have hrz,j∗−cj∗pkj∗=hrz,j′−cj′pkj∗. By the homomorphic properties of h in Definition 6, it follows that hrz,j∗−cj∗rj∗=hrz,j′−cj′rj∗. If rz,j∗−cj∗rj∗≠rz,j′−cj′rj∗ and rz,j∗−cj∗rj∗,rz,j′−cj′rj∗∈Dxm, then A′ finds a collision for h.
Next, we analyze the probability ofrz,j∗−cj∗rj∗≠rz,j′−cj′rj∗. By Lemma 5.2 in [47], we know that there is a distinct private key rj′ such that pkj=hrj′=hrj∗ with overwhelming probability. And by Lemma 5, if the private key rj∗ satisfies rz,j∗−cj∗rj∗=rz,j′−cj′rj∗, then for another private key rj′, we have rz,j∗−cj∗rj′≠rz,j′−cj′rj′. By Theorem 6.5 from [47], it is statistically impossible to distinguish which one of rj′ and rj∗ is used by the signer, and thus the probability of rz,j∗−cj∗rj∗≠rz,j′−cj′rj∗ is at least 1/2−n−ω1. And for any response from HO, si∈Dc, then by Lemma 2, we have rz,j∗−cj∗rj∗∞, rz,j′−cj′rj∗∞≤mn1.5logn, i.e., rz,j∗−cj∗rj∗, rz,j′−cj′rj∗∈Dym⊂Dxm, which implies that A′ finds a solution to Colh,Dx.
From the above analysis, we know that the probability ofA′ breaking Colh,Dx via A calling SO is at least ε−p/Dc, while the probability of A′ breaking Colh,Dx via A calling HO is at least,(27)12−n−ω1ε−1Dcε−1/Dcψ+3Nζ−1Dc.
By comparing formulas (26) and (27), we have the inequality (26) > (27). Thus, the probability of A′ running A to solve Colh,Dx successfully is,(28)ε′≥12−n−ω1ε−1Dcε−1/Dcψ+3Nζ−1Dc.


## 6. Discussion

From Theorem4, it is known that if an adversary succeeds in forging an RS against the proposed scheme, then the challenger can find a collision for a randomly chosen hash function ha∗ in HD,Dx,m. From [29], solving Colh,Dx is equivalent to finding a vector u∈Λq⊥Α on lattice Λq⊥Α=u∈Zmns.t.Au=0modq satisfying u∞≤2mn1.5logn+nlog2n where Α=Rota1Rota2…Rotam∈Zqn×nm, ai is the i-th component of a, i∈m.It was shown in [49] that in a reasonable amount of time, the algorithm for finding short vectors on a random lattice will generate a vector no less than 1.01n times the shortest vector over the lattice. Furthermore, based on the experiments of [49], Micciancio and Regev [50] conduct experiments on lattices very similar to Λq⊥Α, and proves that the length of the shortest vector, which can be found on Λq⊥Α by using the well-known lattice reduction algorithm, is z2≥minq,22nlogqlog1.01 and the corresponding z∞ at least,(29)minq,22nlogqlog1.01⋅nlogqlog1.01−1/4.Therefore, in order to makeColh,Dx be intractable, we should set the parameters in such a manner that requires 2mn1.5logn+nlog2n to be smaller than formula (29). For example, n=512, q≈241, then calculate 2mn1.5logn+nlog2n≈220.1, while the infinite norm of the shortest vector z∞ that can be found by formula (29) is around 229.6. Table 1 gives several sets of parameter settings and security levels for our scheme.Table 1
Parameter setting for our scheme.
Parameternq≈mThe vector length needed to break RSThe shortest vector length that can be foundSecurity level (bits)Recommended choice12827916218.4219.2802562438219.1220.3805122415220.1229.612810242738222.4259.9192


## 7. Efficiency

In this section, in respect of efficiency and security, we compare our scheme with five lattice-based RS schemes without trapdoors: the RS schemes of [37, 38, 40] and the two RS schemes AM1 and AM2 of [41]. The comparison results of storage overhead and computational overhead are listed in Table 2 and 3, respectively. λ is a security parameter, n>λ is a power of 2, N is the number of ring members, and q is a large prime number. In estimating the computational efficiency of each scheme, we mainly focus on the relatively time-consuming operations, such as polynomial inversion and polynomial-polynomial multiplication, while ignoring the less time-consuming operations such as polynomial-polynomial addition and cryptographic hash operation H. The notation Tpoly−inv denotes the computational overhead of running polynomial-polynomial multiplication in D once, Tpoly−mul denotes the computational overhead of running polynomial inversion once, normally Tpoly−inv>Tpoly−mul. Tv denotes the time spent in performing λ times sanity checks of parameters in the signing phase of AM2. Tc denotes the computational overhead of selecting a compliant signing key in the signing phase of AM2.Table 2
Comparison of storage overhead and security.
SchemePublic key sizePrivate key sizeSignature sizeUA-CSAEU-IC[37]OnlogqOnlognOlogNnnlog2nYesYes[38]OnlogqOnOlog5Nnlog2nYesYes[40]OnlogqOnOlogNnlognqYesYesAM1 of [41]OnlognlogqOnlognONnlognlogn1.5log2nYesNoAM2 of [41]OλnlognlogqOλnlognONnlognlogn1.5log2nYesYesOursOnlogqOnlognlognONnlogn1.5lognYesYesTable 3
Comparison of computational overhead at security levelλ=128.
SchemeKey generation costSignature costVerification cost[38]438Tpoly−mul60N+9660Tpoly−mul6N+96Tpoly−mulAM1 of [41]21Tpoly−mul+Tpoly−inv63NTpoly−mul21NTpoly−mulAM2 of [41]λ21Tpoly−mul+Tpoly−inv/263NTpoly−mul+Tv+Tc21NTpoly−mulOurs5Tpoly−mul15NTpoly−mul5NTpoly−mulFrom Table2, the signature size of [37, 38, 40] is OlogN, while the signature size of AM1, AM2 and ours is ON. Without loss of generality, n≥nlogn, thus compared with AM1, AM2, our scheme has smaller public/private key size and signature size.These schemes [37, 38, 40] all use complex and bloated zero-knowledge proofs, and it is very difficult for us to calculate their computational overheads. Among these schemes [37, 38, 40], only the relatively concise scheme of [38] gives its computational overheads analysis. Therefore, we only compare the computational cost of [38, 41] and our scheme. We adopt the calculation method of efficiency in [38], and reduce the operations of KeyGen, Sign and Verify to polynomial-polynomial multiplication operations. To make the comparison results more intuitive, the parameters of [38, 41] and ours are set under the same security level λ=128. Here, n in [38], AM, and ours are set to 256, 128, and 512, respectively; m in [38], AM, and ours are set to 15, 21, and 5, respectively. In terms of KeyGen, Sign and Verify, our scheme obviously has the smallest computational cost as shown in Tables 3 and 4.Table 4
Comparison of approximate computational costs under ring sizeN=27.
SchemeKey generation costSignature costVerification cost[38]438Tpoly−mul17340Tpoly−mul864Tpoly−mulAM1 of [41]21Tpoly−mul+Tpoly−inv8064Tpoly−mul2688Tpoly−mulAM2 of [41]λ21Tpoly−mul+Tpoly−inv/28064Tpoly−mul+Tv+Tc2688Tpoly−mulOurs5Tpoly−mul1920Tpoly−mul640Tpoly−mulTo make the comparison results more intuitive, Figures1 and 2 show the comparison between [38, 41] and ours in terms of computational overhead under different ring sizes.Figure 1
Comparison of computational overhead in the signing phase.Figure 2
Comparison of computational overhead in the verification phase.


## 8. Conclusions

Although lattice-based RS schemes are resistant to attacks by quantum computers, there still exists a big gap between them and the schemes that are based on traditional number-theoretic assumptions with respect to computational efficiency. To further boost the computational efficiency of RS on lattice, this work constructs a lattice-based RS scheme without trapdoors under the random oracle model. Based on a collision-resistant hash function on ideal lattice, our scheme is designed via the FSwA protocol. Our scheme avoids the use of trapdoors or sampling techniques that have high computational overhead and does not involve complex zero-knowledge proofs which are usually used in RS schemes without trapdoors. The proposed scheme is more concise and efficient. Meanwhile, in terms of anonymity and unforgeability, our scheme is proven to satisfy the strongest UA-CSA and EU-IC, respectively. Next, we plan to investigate NTRU lattice-based RS scheme without trapdoors, which will be the first combination of NTRU lattice and RS without trapdoors.



---

*Source: 6547464-2022-09-19.xml*