# Fuzzy Identity-Based Ring Signature from Lattices

Authors: Chengtang Cao; Lin You; Gengran Hu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

In this paper, a construction of a fuzzy identity-based ring signature scheme (LFIBRS) is proposed. Our LFIBRS combines the characteristics of both the fuzzy identity-based signature (FIBS) and the ring signature. On the one hand, a signature issued under an identityID can be verified by any identity ID′ that is “close enough” to the identity ID. Since biometric identification is the well-known most popular and reliable identification method, our LFIBRS can be applied in such a situation whenever it is required for official audit or supervision that the signer’s real identity is needed to be authenticated. On the other hand, LFIBRS provides anonymity under the random oracle model. In addition, LFIBRS provides unforgeability under the small integer solution (SIS) lattice hardness assumption which can resist large-scale quantum computer attacks in the future.


---

## Body

## 1. Introduction

Ring signatures, which were first suggested by Rivest, Shamir, and Tauman [1], allow signing a message on behalf of a spontaneous set of signers, without breaking the anonymity of the signatory. Recently, many versions of ring signature schemes based on this concept have been constructed.Nevertheless, numerous ring signature schemes concern classical number theory or algebraic mathematical assumptions, such as large integer factoring problem [1, 2], discrete logarithm problem [3–5], and bilinear pairing problems [6–10]. None of the schemes are secure with the onset of powerful quantum computers. Among the current postquantum cryptographic candidates, lattice-based cryptography has attracted significant attention of cryptographers recently. In 2008, the first ring signature scheme on lattice was constructed by Gentry et al. [11] and then a lot of ring signature schemes have been constructed [12–14]. Shamir [15] introduced an identity-based cryptosystem. Later, Sahai and Waters [16] put forward the concept of fuzzy identity-based encryption (FIBE), and they regarded identities as a set of biometric attributes rather than any string. Since then, many kinds of fuzzy identity-based signature schemes have been constructed [17–21]. As one of the most promising research alternatives of postquantum cryptography, lattice-based cryptography has attracted great attention due to its several potential advantages: asymptotic efficiency, the worst-case hardness hypothesis, and the security against quantum computing.How to design a secure and efficient lattice-based cryptosystem is a very interesting and challenging problem. In this manuscript, based on the work of [21, 22], a fuzzy identity ring signature scheme based on the computational difficulty problem on lattices is constructed by combining the characteristics of fuzzy identity signature and ring signature.


### 1.1. Related Work

Wang et al. [23] proposed a lattice-based ring signature scheme in the Bonsai tree model, which was based on the hard assumption of SIS problem; meanwhile, unforgeability had been proved in both the random oracle and standard model. Wang [24] and Jia et al. [22] proposed identity-based ring signature scheme from lattice which was based on the hard assumption of SIS problem. As we know, Yao and Li [19] constructed the first FIBS scheme based on the hard assumption of SIS problem. By using the Bonsai tree techniques, they proved that their scheme was secure in the random oracle model. Recently, Zhang et al. [21] proposed an extended version of Yao and Li’s FIBS scheme and claimed that it could capture more expressive attributes in a large universe. Besides, their version was proved to be strongly unforgeable against selective chosen-identity and adaptive chosen-message attacks (SU-sID-CMA) secure in the standard model.


### 1.2. Contributions

In this paper, we propose a fuzzy identity-based ring signature scheme (LFIBRS) based on the hard assumption of SIS problem and prove that it is unforgeable in the random oracle model. In this work, we focus on combining the characteristics of ring signature and the fuzzy identity-based signature from lattices, and it makes our scheme be able to provide biometric authentication and maintain anonymity at the same time.


### 1.3. Structure of the Paper

In Section2, some mathematical symbols, integer lattices, and statistical distance are defined. Section 3 gives the framework of the signature scheme. The construction of our signature scheme is described in Section 4. The security of our LFIBRS is proved in Section 5. Finally, some comparisons with some other referred works and conclusion remarks are given.


## 1.1. Related Work

Wang et al. [23] proposed a lattice-based ring signature scheme in the Bonsai tree model, which was based on the hard assumption of SIS problem; meanwhile, unforgeability had been proved in both the random oracle and standard model. Wang [24] and Jia et al. [22] proposed identity-based ring signature scheme from lattice which was based on the hard assumption of SIS problem. As we know, Yao and Li [19] constructed the first FIBS scheme based on the hard assumption of SIS problem. By using the Bonsai tree techniques, they proved that their scheme was secure in the random oracle model. Recently, Zhang et al. [21] proposed an extended version of Yao and Li’s FIBS scheme and claimed that it could capture more expressive attributes in a large universe. Besides, their version was proved to be strongly unforgeable against selective chosen-identity and adaptive chosen-message attacks (SU-sID-CMA) secure in the standard model.


## 1.2. Contributions

In this paper, we propose a fuzzy identity-based ring signature scheme (LFIBRS) based on the hard assumption of SIS problem and prove that it is unforgeable in the random oracle model. In this work, we focus on combining the characteristics of ring signature and the fuzzy identity-based signature from lattices, and it makes our scheme be able to provide biometric authentication and maintain anonymity at the same time.


## 1.3. Structure of the Paper

In Section2, some mathematical symbols, integer lattices, and statistical distance are defined. Section 3 gives the framework of the signature scheme. The construction of our signature scheme is described in Section 4. The security of our LFIBRS is proved in Section 5. Finally, some comparisons with some other referred works and conclusion remarks are given.


## 2. Preliminaries

### 2.1. Notations

In this section, we make use of the following notations:i: The set 1,2,…,ix←S: x is sampled uniformly at random from the set Sz: The Euclidean norm of zA: The norm of A as the norm of its longest column A=maxiAiA˜: The matrix after Gram-Schmidt orthogonalization of matrix Afn=ωgn: If limn⟶∞=gn/fn=0fn=O˜gn: If fn=gn⋅polylogn


### 2.2. Integer Lattices

Definition 1.
LetB=b1|b2|⋯|bm∈ℝm×m be a matrix with m linearly independent vectors. The m-dimensional lattice Λ generated by B is as follows:(1)Λ=ℒB=y∈ℝm:∃s∈ℤm,y=Bs.Definition 2.
For primeq≥2 and matrix A∈ℤn×m, define(2)Λq⊥A=y∈ℤm:Ay=Omodq.
Fors>0, define the Gaussian function on ℝm with center c:∀e∈ℝm, ρs,ce=exp−πe−c2/s2. For m-dimensional lattice Λ, define ρs,cΛ=∑e∈Λρs,ce. For c∈ℝm and s>0, define the discrete Gaussian distribution over Λ as follows: ∀e∈Λ,DΛ,s,c=ρs,ce/ρs,cΛ. For convenience, if c=O, we denote DΛ,s,c as DΛ,s.


### 2.3. Lattice-Related Algorithms

How to obtain a matrixA with a low Gram-Schmidt norm basis for Λq⊥A was introduced by Ajtai [25], and two improved algorithms were proposed by [26, 27], respectively.Lemma 1 (see [26]).
Let integersq≥3 be odd, n≥1, and m=2n⌈logq⌉. There exists a PPT algorithm TrapGenq,n,m that outputs A and TA such that A is statistically close to a uniform matrix in ℤqn×m and TA∈ℤqm×m is a short basis for Λq⊥A, satisfying TA˜≤Onlogq with all but a negligible probability in n.In this subsection, we recall several useful facts on lattices in the literatures [1, 28], in order to generate another short basis for a lattice which contains a sublattice isomorphic to the original.Lemma 2 (Lemma 3.2 of [28]).
On inputA∈ℤqn×m, whose columns generate the entire group ℤqn and an arbitrary B∈ℤqn×m′, given a basis TA of Λq⊥A, there is a deterministic polynomial-time algorithm ExtBasisTA,A′=A|B that outputs a basis TA′ for Λq⊥A′⊆ℤm+m′ such that TA′˜=TA˜. Moreover, this statement holds even for any given permutation of the columns of A′.Lemma 3 (Lemma 3.3 of [28]).
On inputA∈ℤqn×m, s≥TA˜⋅ωlogn. Given a basis TA of Λq⊥A, there is a PPT algorithm RandBasisA,TA,s that outputs a basis TA′ for Λq⊥A such that TA′˜≤sm and no information specific to TA is leaked.We adopt the preimage sampling lemma from the discrete Gaussian distribution over lattices, which is shown in [11].Lemma 4 (see [11]).
Assume integerq≥2,A∈ℤqn×m, and real 0<ϵ<1. Let TA be a short basis for Λq⊥A; parameter s≥TA˜⋅ωlogn. Then, for c∈ℝm,u∈ℤqm,(1)
Prx←DΛ,s,c:x−c>sm<1+ϵ/1−ϵ⋅2−m(2)
A PPT algorithmSampleGauA,TA,s,c returns e∈Λq⊥A drawn from a distribution statistically close to DΛq⊥A,s,c(3)
A PPT algorithmSamplePreA,TA,s,c returns e∈ΛquA sampled from a distribution statistically close to DΛquA,sIn [22], Lemma 4 is extended to the matrix sampling algorithm, which is repeated as follows.Lemma 5 (see [22]).
On inputA∈ℤqn×m, s≥T˜⋅ωlogn. Given a short basis T for Λq⊥A and arbitrary matrix V∈ℤqn×k, there is a polynomial-time algorithm SampleMatPreA,T,s,V, which outputs a matrix S∈ℤqm×k, so that AS=V, V and DΛ⊥A are statistically close, and V≤sm holds with overwhelming probability.Rejection sampling is an important technology of lattice-based signature scheme, which is proposed by Lyubashevsky in [29]. In the signing process, we output the candidate signature in a certain probability without using a preimage sampling algorithm; hence, the distribution of the output signature is independent of the private key of the signer. With regard to the technique of rejecting sampling, we use the two following results.Lemma 6 (Lemma 4.4 of [29]).
For anyσ>0 and integer m, the following inequalities hold:(1)
Prx←Dσ:x>wσlogm<2−ωlogm(2)
For anyz∈ℤm and σ>log3m, Dσm<2−m+1 holds(3)
Prx←Dσm:x>2σlogm<2−mTheorem 1 (Theorem 4.6 of [29]).
LetV be a subset of ℤm in which all elements have norms less than T, let σ be some element in ℝ such that σ=ωTlogm, and let h:V⟶ℝ be a probability distribution. Then there exists a constant M=O1 such that the distribution of the following algorithm A,(1)
v←h(2)
z←Dv,σm(3)
outputz,v with probability minDσmz/MDv,σmz,1
is within the statistical distance2−ωlogm/M of the distribution of the following algorithm ℱ:(1)
v←h(2)
z←Dσm(3)
outputz,v with probability 1/M
Moreover, the probability thatA outputs something is at least 1−2−ωlogm/M.


### 2.4. Statistical Distance

The statistical distance measures how different two probability distributions are. In order to be employed in the anonymity of our scheme, we recall it as follows.Definition 3 (Definition 8.5 of [30]).
LetX and X′ be two random variables over a countable set S. The statistical distance between X and X′ is defined by(3)ΔX,X′=12∑x∈SPrX=x−PrX′=x.
The following lemmas show that the statistical distance cannot be increased by a randomized algorithm.Lemma 7 (Proposition 8.9 of [30]).
LetX1,X2,…,Xk and Y1,Y2,…,Yk be two lists of totally independent random variables. Then,(4)ΔX1,X2,…,Xk,Y1,Y2,…,Yk≤∑i=1kΔXi,Yi.Lemma 8 (Proposition 8.10 of [30]).
Assume thatX and X′ are two random variables over set S. For any (possibly randomized) function f with domain S, the statistical distance between fX and fX′ is at most(5)ΔfX,fX′≤ΔX,X′.


### 2.5. The SIS Problem

The SIS problem is as hard as the worst-case lattice problem; it was proved by Ajtai [25] for the first time,and then by Micciancio and Regev [31] and Gentry et al. [11]. We recall it as follows.Definition 4.
The SIS problem in the Euclidean norm is that, given an integerq, a matrix A∈ℤqn×m, and a positive real β, the goal is to find a nonzero vector e∈ℤm satisfying Ae=Omodq, and e≤β.Lemma 9 (Theorem 5.16 of [31]).
For poly-boundedm, β=polyn, and prime q≥β⋅ωnlogn, the average-case SISq,n,m,β problem is as hard as approximating the shortest independent vector problem SIVPγ to within certain γ=β⋅O˜n factor.


## 2.1. Notations

In this section, we make use of the following notations:i: The set 1,2,…,ix←S: x is sampled uniformly at random from the set Sz: The Euclidean norm of zA: The norm of A as the norm of its longest column A=maxiAiA˜: The matrix after Gram-Schmidt orthogonalization of matrix Afn=ωgn: If limn⟶∞=gn/fn=0fn=O˜gn: If fn=gn⋅polylogn


## 2.2. Integer Lattices

Definition 1.
LetB=b1|b2|⋯|bm∈ℝm×m be a matrix with m linearly independent vectors. The m-dimensional lattice Λ generated by B is as follows:(1)Λ=ℒB=y∈ℝm:∃s∈ℤm,y=Bs.Definition 2.
For primeq≥2 and matrix A∈ℤn×m, define(2)Λq⊥A=y∈ℤm:Ay=Omodq.
Fors>0, define the Gaussian function on ℝm with center c:∀e∈ℝm, ρs,ce=exp−πe−c2/s2. For m-dimensional lattice Λ, define ρs,cΛ=∑e∈Λρs,ce. For c∈ℝm and s>0, define the discrete Gaussian distribution over Λ as follows: ∀e∈Λ,DΛ,s,c=ρs,ce/ρs,cΛ. For convenience, if c=O, we denote DΛ,s,c as DΛ,s.


## 2.3. Lattice-Related Algorithms

How to obtain a matrixA with a low Gram-Schmidt norm basis for Λq⊥A was introduced by Ajtai [25], and two improved algorithms were proposed by [26, 27], respectively.Lemma 1 (see [26]).
Let integersq≥3 be odd, n≥1, and m=2n⌈logq⌉. There exists a PPT algorithm TrapGenq,n,m that outputs A and TA such that A is statistically close to a uniform matrix in ℤqn×m and TA∈ℤqm×m is a short basis for Λq⊥A, satisfying TA˜≤Onlogq with all but a negligible probability in n.In this subsection, we recall several useful facts on lattices in the literatures [1, 28], in order to generate another short basis for a lattice which contains a sublattice isomorphic to the original.Lemma 2 (Lemma 3.2 of [28]).
On inputA∈ℤqn×m, whose columns generate the entire group ℤqn and an arbitrary B∈ℤqn×m′, given a basis TA of Λq⊥A, there is a deterministic polynomial-time algorithm ExtBasisTA,A′=A|B that outputs a basis TA′ for Λq⊥A′⊆ℤm+m′ such that TA′˜=TA˜. Moreover, this statement holds even for any given permutation of the columns of A′.Lemma 3 (Lemma 3.3 of [28]).
On inputA∈ℤqn×m, s≥TA˜⋅ωlogn. Given a basis TA of Λq⊥A, there is a PPT algorithm RandBasisA,TA,s that outputs a basis TA′ for Λq⊥A such that TA′˜≤sm and no information specific to TA is leaked.We adopt the preimage sampling lemma from the discrete Gaussian distribution over lattices, which is shown in [11].Lemma 4 (see [11]).
Assume integerq≥2,A∈ℤqn×m, and real 0<ϵ<1. Let TA be a short basis for Λq⊥A; parameter s≥TA˜⋅ωlogn. Then, for c∈ℝm,u∈ℤqm,(1)
Prx←DΛ,s,c:x−c>sm<1+ϵ/1−ϵ⋅2−m(2)
A PPT algorithmSampleGauA,TA,s,c returns e∈Λq⊥A drawn from a distribution statistically close to DΛq⊥A,s,c(3)
A PPT algorithmSamplePreA,TA,s,c returns e∈ΛquA sampled from a distribution statistically close to DΛquA,sIn [22], Lemma 4 is extended to the matrix sampling algorithm, which is repeated as follows.Lemma 5 (see [22]).
On inputA∈ℤqn×m, s≥T˜⋅ωlogn. Given a short basis T for Λq⊥A and arbitrary matrix V∈ℤqn×k, there is a polynomial-time algorithm SampleMatPreA,T,s,V, which outputs a matrix S∈ℤqm×k, so that AS=V, V and DΛ⊥A are statistically close, and V≤sm holds with overwhelming probability.Rejection sampling is an important technology of lattice-based signature scheme, which is proposed by Lyubashevsky in [29]. In the signing process, we output the candidate signature in a certain probability without using a preimage sampling algorithm; hence, the distribution of the output signature is independent of the private key of the signer. With regard to the technique of rejecting sampling, we use the two following results.Lemma 6 (Lemma 4.4 of [29]).
For anyσ>0 and integer m, the following inequalities hold:(1)
Prx←Dσ:x>wσlogm<2−ωlogm(2)
For anyz∈ℤm and σ>log3m, Dσm<2−m+1 holds(3)
Prx←Dσm:x>2σlogm<2−mTheorem 1 (Theorem 4.6 of [29]).
LetV be a subset of ℤm in which all elements have norms less than T, let σ be some element in ℝ such that σ=ωTlogm, and let h:V⟶ℝ be a probability distribution. Then there exists a constant M=O1 such that the distribution of the following algorithm A,(1)
v←h(2)
z←Dv,σm(3)
outputz,v with probability minDσmz/MDv,σmz,1
is within the statistical distance2−ωlogm/M of the distribution of the following algorithm ℱ:(1)
v←h(2)
z←Dσm(3)
outputz,v with probability 1/M
Moreover, the probability thatA outputs something is at least 1−2−ωlogm/M.


## 2.4. Statistical Distance

The statistical distance measures how different two probability distributions are. In order to be employed in the anonymity of our scheme, we recall it as follows.Definition 3 (Definition 8.5 of [30]).
LetX and X′ be two random variables over a countable set S. The statistical distance between X and X′ is defined by(3)ΔX,X′=12∑x∈SPrX=x−PrX′=x.
The following lemmas show that the statistical distance cannot be increased by a randomized algorithm.Lemma 7 (Proposition 8.9 of [30]).
LetX1,X2,…,Xk and Y1,Y2,…,Yk be two lists of totally independent random variables. Then,(4)ΔX1,X2,…,Xk,Y1,Y2,…,Yk≤∑i=1kΔXi,Yi.Lemma 8 (Proposition 8.10 of [30]).
Assume thatX and X′ are two random variables over set S. For any (possibly randomized) function f with domain S, the statistical distance between fX and fX′ is at most(5)ΔfX,fX′≤ΔX,X′.


## 2.5. The SIS Problem

The SIS problem is as hard as the worst-case lattice problem; it was proved by Ajtai [25] for the first time,and then by Micciancio and Regev [31] and Gentry et al. [11]. We recall it as follows.Definition 4.
The SIS problem in the Euclidean norm is that, given an integerq, a matrix A∈ℤqn×m, and a positive real β, the goal is to find a nonzero vector e∈ℤm satisfying Ae=Omodq, and e≤β.Lemma 9 (Theorem 5.16 of [31]).
For poly-boundedm, β=polyn, and prime q≥β⋅ωnlogn, the average-case SISq,n,m,β problem is as hard as approximating the shortest independent vector problem SIVPγ to within certain γ=β⋅O˜n factor.


## 3. System Framework and Security Model of LFIBRS Scheme

A fuzzy identity-based ring signature scheme consists of the following four probabilistic polynomial-time (PPT) algorithms:SetUpq,n,m: The Private Key Generator (PKG) runs a PPT algorithm that takes the security parameter n as input and generates the system parameters PP, an error tolerance parameter k, and master keys MK. The system parameters PP are made public and master keys MK are kept secret.KeyExtID,PP,MK: It is a PPT algorithm that takes an identity ID, the public parameters PP, and the master keys MK as input and outputs secret keys SK and public key AID associated with the ID.Sign(μ,sk,PK,PP: It is a PPT algorithm that takes the public parameters PP, the public keys PK=PKIDii∈l corresponding to the identities of l ring members, the secret keys SK associated with an identity ID, and a message μ as input and outputs a signature σ.Verifyμ,σ,ID′,PP,PK: It is a deterministic algorithm that takes the public parameters PP, an fuzzy identity ID′s, the message μ, the public keys PK, and the corresponding signature σ as input and outputs “1” or “0.”The correctness of a ring signature scheme with fuzzy identity means that the verification algorithm always outputs “1” for a legal signature and “0” for an illegal signature.


### 3.1. Security Properties

A security ring signature must satisfy anonymity and unforgeability. The formal definition of the security model is given as follows.Definition 6 (anonymity).
If there is no polynomial-time adversaryA to win the following games with an advantage that cannot be ignored, the LFIBRS scheme is signer-ambiguous.(1)
Setup: input system parameters n and C to generate and send public parameter PP and the maximum possible user set UN=ID1,ID2,…,IDN to A.(2)
Query: A performs a polynomially bounded number of queries.(3)
Challenge: C selects the message μ, U∗=IDi1∗,IDi2∗,…,IDil∗⊆UN, and uses the master key MK to generate the secret key SKi0 and SKi1 which corresponds to IDi0 and IDi1. C randomly selects b∈0,1 and then calls the signature algorithm to generate the signature σib.(4)
Guess: A outputs bit b′ as a guess of b. If b′=b, then A wins the game.
The advantage is defined asAdvA=Prb′=b−1/2.Definition 7 (unforgeability).
If there is no polynomial time adversaryA to win the following games with an advantage that cannot be ignored, then the LFIBRS scheme is said to be unforgeable.(1)
Setup: C exposes parameters PP and identity set UN and sends them to A.(2)
Query: adversary A can perform polynomial query:Private key query:C calls the private key extraction algorithm, obtains the secret key SK corresponding to the identity ID, and returns it to ASignature query:C calls the signature algorithm to get the signature σ of the message μ and returns it to A(3)
Forgery: the adversary A submits i∗,ID′∗,PK,μ∗,σ∗, if the following conditions are true:(1)
σ∗ is a legal signature(2)
A did not query the private key of ID′∗(3)
A did not query ID′∗ and μ∗; then A won the game
The advantage is defined asAdvA=PrLFIBRS−Verifyμ,σ∗,ID′∗,PP,PK=1.


## 3.1. Security Properties

A security ring signature must satisfy anonymity and unforgeability. The formal definition of the security model is given as follows.Definition 6 (anonymity).
If there is no polynomial-time adversaryA to win the following games with an advantage that cannot be ignored, the LFIBRS scheme is signer-ambiguous.(1)
Setup: input system parameters n and C to generate and send public parameter PP and the maximum possible user set UN=ID1,ID2,…,IDN to A.(2)
Query: A performs a polynomially bounded number of queries.(3)
Challenge: C selects the message μ, U∗=IDi1∗,IDi2∗,…,IDil∗⊆UN, and uses the master key MK to generate the secret key SKi0 and SKi1 which corresponds to IDi0 and IDi1. C randomly selects b∈0,1 and then calls the signature algorithm to generate the signature σib.(4)
Guess: A outputs bit b′ as a guess of b. If b′=b, then A wins the game.
The advantage is defined asAdvA=Prb′=b−1/2.Definition 7 (unforgeability).
If there is no polynomial time adversaryA to win the following games with an advantage that cannot be ignored, then the LFIBRS scheme is said to be unforgeable.(1)
Setup: C exposes parameters PP and identity set UN and sends them to A.(2)
Query: adversary A can perform polynomial query:Private key query:C calls the private key extraction algorithm, obtains the secret key SK corresponding to the identity ID, and returns it to ASignature query:C calls the signature algorithm to get the signature σ of the message μ and returns it to A(3)
Forgery: the adversary A submits i∗,ID′∗,PK,μ∗,σ∗, if the following conditions are true:(1)
σ∗ is a legal signature(2)
A did not query the private key of ID′∗(3)
A did not query ID′∗ and μ∗; then A won the game
The advantage is defined asAdvA=PrLFIBRS−Verifyμ,σ∗,ID′∗,PP,PK=1.


## 4. Construction of LFIBRS

In this part, we present our construction of LFIBRS from lattice. The LFIBRS consists of four probability polynomial-time algorithmsSetup, KeyExt, Sign, and Verify. We have incorporated different notations of the proposed LFIBRS scheme in the following.


### 4.1. LFIBRS Setup

This phase can be described as follows:Step 1. For i∈l, run Trapgenq,n,m to generate a uniformly random matrix Ei∈ℤqn×m together with a short basis TEi for Λ⊥Ei, such that TEi˜≤Onlogq.Step 2. Run Trapgenq,n,m to generate a uniformly random matrix B∈ℤqn×m together with a short basis TB for Λ⊥B, such thatTB˜≤Onlogq.Step 3. For i∈l, randomly choose matrix Fi in ℤqn×m.Step 4. Randomly choose matrices B,C in ℤqn×m and D in ℤqm×m.Step 5. Select hash functions H1:ℤqm⟶ℤqn×n, H2:ℤqml×ℤqm⟶ℤqn×m, H3:0,1∗⟶ℤqn, and H4:ℤq2m×0,1∗⟶v∈ℤqm:v≤t.Step 6. Select an error tolerance parameter k such that k≤l−1.Step 7. Output public parameters PP and master keys MK:PP=Ei,Fii∈l,B,C,D,H1,H2,H3,H4,k and MK=TEii∈l,TB. Public parameters are made public and master keys are kept secret.


### 4.2. LFIBRS-KeyExt

Input a user whose identifyID=ID1,ID2,…,IDl; IDi∈ℤqm and i∈l. Let us do the steps as follows:Step 1. For i∈l, compute Gi=Ei|H1IDiFi, Gi∈ℤqn×2m.Step 2. For i∈l, compute matrix TGi using algorithm RandBasisGi,ExtBasisTEi,Ei,s0.Step 3. Compute PKID=B|H2IDD, PKID∈ℤqn×2m. We remark that PKID=B|H2IDD plays the role of the associated public key.Step 4. Compute the matrix TPKID using algorithm RandBasisPKID,ExtBasisTB,B,s0.Step 5. Run SampleMatprePKID,TPKID,s,C to generate SID∈ℤq2m×m and PKIDSID=C, such that SID≤s2m.Step 6. Output PKID and SK=TGi,Gii∈l,SID. PKID is the ID’s public key and SK=TGi,Gii∈l,SID are the corresponding secret keys.


### 4.3. LFIBRS-Sign

Input a messageμ and the public keys PK=PKIDii∈l corresponding to the identities of l ring members where the identity IDππ∈l of the real signer is related to the public key PKIDπ and the secret keys SKπ=TGi,Gii∈l,SIDπ. The signing process is as follows:Step 1. Compute v1=H3μ,PK.Step 2.v1=v11,v12,…,v1m∈ℤqm. The Shamir’s secret sharing scheme is applied to every coordinate v1a of v1, that is, when a∈m, the polynomial with degree k−1 is constructed in ℤqm, such that pa0=v1a.Step 3. Construct the a-th share vector, va^=p1a,p2a,…,pma∈ℤqm. Thus, for J⊆l and k=J≤l−1, there are fractional Lagrangian coefficients La such that v1=∑a∈JLava^modq.Step 4. For i∈l, call algorithm SamplePreGi,TGi,va^,s2 to calculate ei∈ℤq2m.Step 5. Compute v=H4∑i∈lPKIDiei,μ.Step 6. Let zπ=SIDπ⋅v+eπ, and call algorithm A in Theorem 1; if there is output, output zπ; otherwise, reselect the public key and go to the first step.Step 7. For i∈l\π, let zi=ei.Step 8. Output σ=z1,z2,…,zl,v.


### 4.4. LFIBRS-Verify

Input the fuzzy identityID′=ID1′,ID2′,…,IDl′, public parameters PP, message μ, the public keys PK=PKIDii∈l, and the signature σ. The verification process is given as follows:Step 1. For i∈l, verify zi≤2s22m. If it is true, continue to the next step. Otherwise, stop.Step 2. For i∈l, calculate Gi′=Ei|H1IDi′Fi.Step 3. Let E⊆G1′,G2′,…,Gl′ and E=k; if there is E such that ∑Ga′∈ELaGa′za=H3μ,PK, La=∏a∈a:Ga′∈E,i≠ai/i−a, continue to the next step. Otherwise, stop.Step 4. If v=H4∑i∈lPKIDizi−cv,μ, output “1.” Otherwise, output “0.”


### 4.5. LFIBRS-Parameters

The safety parameter of scheme FIBRS isn, and other parameters are set as follows:(1)
SinceTrapGenq,n,m is called, m=2n⌈logq⌉ is set by Lemma 1.(2)
To ensure the difficulty of SIS problem, setq≥βωnlogn, β=2s12m, by Lemma 9(3)
BecauseRandBasisPKID,ExtBasisTB,B,s0 is called, by Lemmas 2 and 3, set s0≥Ologn⋅ωlogn(4)
BecauseSampleMatprePKID,TAID,s,C is called, by Lemma 5, set s≥s02m⋅ωlogn(5)
Because the signature algorithm needs Lemma4 and Theorem 1, set s1=ωTlog2m(6)
Due to callSamplePreGi,TGi,va^,s2, set s2=s12m⋅ωlog2m


### 4.6. LFIBRS-Correctness

The correctness analysis is briefly described as follows:(1)
According to Theorem1 and Lemma 6, the signature will output zj with overwhelming probability.(2)
According to Lemma4, when the real identity can pass the verification in step 1 of the verification process, the next step can be continued.(3)
The following formula is established:(6)∑i∈lPKIDizi−Cv=∑i∈l\πPKIDizi+PKIDπzπ−Cv=∑i∈l\πPKIDiei+PKIDπeπ=∑i∈lPKIDiei.


## 4.1. LFIBRS Setup

This phase can be described as follows:Step 1. For i∈l, run Trapgenq,n,m to generate a uniformly random matrix Ei∈ℤqn×m together with a short basis TEi for Λ⊥Ei, such that TEi˜≤Onlogq.Step 2. Run Trapgenq,n,m to generate a uniformly random matrix B∈ℤqn×m together with a short basis TB for Λ⊥B, such thatTB˜≤Onlogq.Step 3. For i∈l, randomly choose matrix Fi in ℤqn×m.Step 4. Randomly choose matrices B,C in ℤqn×m and D in ℤqm×m.Step 5. Select hash functions H1:ℤqm⟶ℤqn×n, H2:ℤqml×ℤqm⟶ℤqn×m, H3:0,1∗⟶ℤqn, and H4:ℤq2m×0,1∗⟶v∈ℤqm:v≤t.Step 6. Select an error tolerance parameter k such that k≤l−1.Step 7. Output public parameters PP and master keys MK:PP=Ei,Fii∈l,B,C,D,H1,H2,H3,H4,k and MK=TEii∈l,TB. Public parameters are made public and master keys are kept secret.


## 4.2. LFIBRS-KeyExt

Input a user whose identifyID=ID1,ID2,…,IDl; IDi∈ℤqm and i∈l. Let us do the steps as follows:Step 1. For i∈l, compute Gi=Ei|H1IDiFi, Gi∈ℤqn×2m.Step 2. For i∈l, compute matrix TGi using algorithm RandBasisGi,ExtBasisTEi,Ei,s0.Step 3. Compute PKID=B|H2IDD, PKID∈ℤqn×2m. We remark that PKID=B|H2IDD plays the role of the associated public key.Step 4. Compute the matrix TPKID using algorithm RandBasisPKID,ExtBasisTB,B,s0.Step 5. Run SampleMatprePKID,TPKID,s,C to generate SID∈ℤq2m×m and PKIDSID=C, such that SID≤s2m.Step 6. Output PKID and SK=TGi,Gii∈l,SID. PKID is the ID’s public key and SK=TGi,Gii∈l,SID are the corresponding secret keys.


## 4.3. LFIBRS-Sign

Input a messageμ and the public keys PK=PKIDii∈l corresponding to the identities of l ring members where the identity IDππ∈l of the real signer is related to the public key PKIDπ and the secret keys SKπ=TGi,Gii∈l,SIDπ. The signing process is as follows:Step 1. Compute v1=H3μ,PK.Step 2.v1=v11,v12,…,v1m∈ℤqm. The Shamir’s secret sharing scheme is applied to every coordinate v1a of v1, that is, when a∈m, the polynomial with degree k−1 is constructed in ℤqm, such that pa0=v1a.Step 3. Construct the a-th share vector, va^=p1a,p2a,…,pma∈ℤqm. Thus, for J⊆l and k=J≤l−1, there are fractional Lagrangian coefficients La such that v1=∑a∈JLava^modq.Step 4. For i∈l, call algorithm SamplePreGi,TGi,va^,s2 to calculate ei∈ℤq2m.Step 5. Compute v=H4∑i∈lPKIDiei,μ.Step 6. Let zπ=SIDπ⋅v+eπ, and call algorithm A in Theorem 1; if there is output, output zπ; otherwise, reselect the public key and go to the first step.Step 7. For i∈l\π, let zi=ei.Step 8. Output σ=z1,z2,…,zl,v.


## 4.4. LFIBRS-Verify

Input the fuzzy identityID′=ID1′,ID2′,…,IDl′, public parameters PP, message μ, the public keys PK=PKIDii∈l, and the signature σ. The verification process is given as follows:Step 1. For i∈l, verify zi≤2s22m. If it is true, continue to the next step. Otherwise, stop.Step 2. For i∈l, calculate Gi′=Ei|H1IDi′Fi.Step 3. Let E⊆G1′,G2′,…,Gl′ and E=k; if there is E such that ∑Ga′∈ELaGa′za=H3μ,PK, La=∏a∈a:Ga′∈E,i≠ai/i−a, continue to the next step. Otherwise, stop.Step 4. If v=H4∑i∈lPKIDizi−cv,μ, output “1.” Otherwise, output “0.”


## 4.5. LFIBRS-Parameters

The safety parameter of scheme FIBRS isn, and other parameters are set as follows:(1)
SinceTrapGenq,n,m is called, m=2n⌈logq⌉ is set by Lemma 1.(2)
To ensure the difficulty of SIS problem, setq≥βωnlogn, β=2s12m, by Lemma 9(3)
BecauseRandBasisPKID,ExtBasisTB,B,s0 is called, by Lemmas 2 and 3, set s0≥Ologn⋅ωlogn(4)
BecauseSampleMatprePKID,TAID,s,C is called, by Lemma 5, set s≥s02m⋅ωlogn(5)
Because the signature algorithm needs Lemma4 and Theorem 1, set s1=ωTlog2m(6)
Due to callSamplePreGi,TGi,va^,s2, set s2=s12m⋅ωlog2m


## 4.6. LFIBRS-Correctness

The correctness analysis is briefly described as follows:(1)
According to Theorem1 and Lemma 6, the signature will output zj with overwhelming probability.(2)
According to Lemma4, when the real identity can pass the verification in step 1 of the verification process, the next step can be continued.(3)
The following formula is established:(6)∑i∈lPKIDizi−Cv=∑i∈l\πPKIDizi+PKIDπzπ−Cv=∑i∈l\πPKIDiei+PKIDπeπ=∑i∈lPKIDiei.


## 5. Security Analysis

Next, we will prove that the above LFIBRS scheme satisfies anonymity and unforgeability as required.Theorem 2 (anonymity).
For primeq≥3, m=2n⌈logq⌉, and b∈0,1, σb,PP,IDib,PK,SKib,μ are the outputs of the algorithm LFIBRS-SignPP,ID,PK,SKib,μ, where PP is the public parameter, IDib is the identity, SKib is the secret key of the corresponding signature, and μ is the message of the corresponding signature. For any polynomial-time adversary, when SKi0 and SKi1 are unknown, the following formula holds:(7)Δσ0,PP,IDi0,SKi0,μ,σ1,PP,IDi1,SKi1,μ≤n−ω1.Therefore, the proposed LFIBRS scheme is computationally anonymous under the random oracle model.Proof.
The adversaryA is a probabilistic polynomial-time Turing machine, which is allowed to make queries to the following oracles:Setup: C performs the following operations to generate the public parameter PP and all user identities UN and sends them to A.(1)
Determine the maximum possible user setUN=ID1,ID2,…,IDN(2)
Randomly select matricesB,C in ℤqn×m and D in ℤqm×m(3)
Output public parametersPP=B,C,D and UN=ID1,ID2,…,IDNQuery: adversary A can send the following query to C, and C will return the query result to A. Without losing generality, let A not repeat the query. C performs the following operations:Hash query:(1)
A submits a user IDi=ID1i,ID2i,…,IDli to C, and, for j∈l, C selects H1IDji∈ℤqn×n to return it to A(2)
A submits the user IDi to C, and C selects H2IDi∈ℤqn×m to return it to A(3)
A submits a message μ and the public keys PK=PKIDii∈l corresponding to the identities of l ring members, where the identity IDππ∈l to C and C selects v1∈∈ℤqn to return it to A(4)
A submits a message μ and the public keys PK=PKIDii∈l corresponding to the identities of l ring members, and C selects v∈v∈ℤqm:v≤t to return it to AExtract query:A adaptively selects a user IDii∈N to C. C returns the secret key SKIDi of the corresponding user IDi.Sign query:A submits message μ, the identity subset U=IDi1,IDi2,…,IDil⊆UN, and the user IDit∈U to ℬ. ℬ operates as follows:(1)
C runs the algorithm LFIBRS−KeyExt to get the corresponding public keys subring PK=PKIDitt∈l corresponding to the identities of l ring members, where the identity IDitπ∈l(2)
Input the messageμ, public keys subring PK=PKIDitt∈l, and secret key SKIDit; C runs the algorithm LFIBRS−Sign and returns the signature z1,z2,…,zl,v of the user IDitChallenge: C selects μ∗ and the identity subset U∗=IDi1∗,IDi2∗,…,IDil∗⊆UN and uses the master key MK to generate the secret keys SKi0 and SKi1 corresponding to IDi0, where IDi1,IDi0∈U∗. C randomly selects b∈0,1 and then calls the signature algorithm to generate the signature σib.Guess: A outputs bit b′.
Suppose that the signature with secret keySKi0 outputs σ0=σ10,z20,…,zl0,v0 and the signature with secret key SKi1 outputs σ1=z11,z21,…,zl1,v1. σ0,PP,IDi0,PK,SKi0 is abbreviated as σ0. σ1,PP,IDi1,PK,SKi1 is abbreviated as σ1.
To get anonymity, we just need to prove that the signaturesσ0 and σ1 are statistically indistinguishable. From Lemmas 7 and 8 and trigonometric inequality, we can get(8)Δσ0,σ1=Δz10,z20,…,zl0,v0,z11,z21,…,zl1,v1≤Δz10,z20,…,zl0,z11,z21,…,zl1≤Δz10,z20,…,zl0,Ds12ml+Δz11,z21,…,zl1,Ds12ml≤lΔzi0,Ds12m+lΔzi1,Ds12m.
From Theorem1, we can get Δzi0,Ds12m≤2−ωlog2m/M and Δzi1,Ds12m≤2−ωlog2m/M, so(9)lΔzi0,Ds12m+lΔzi1,Ds12m≤2l2−ωlog2mM=n−ω1.
Therefore, the proposed LFIBRS scheme is computationally anonymous under the random oracle model.Theorem 3 (Unforgeability).
For primeq≥3 and m=2n⌈logq⌉ , in time T, if there is a polynomial-time adversary A that can forge the effective signature of LFIBRS scheme with the probability of ϵ, then there is a polynomial-time algorithm ℬ that can solve the SISq,n,m,β problem with the probability of ϵ′ in time T′≈T, where ϵ′≥ϵ−n−ω1 and β=2s12m.Proof.
The proof process is similar to literature [21, 22]. The analysis is as follows.
Suppose that there is a polynomial-time adversaryA that forges the signature of LFIBRS scheme with the probability of ϵ. Next, the polynomial-time algorithm ℬ is constructed to solve the SISq,n,m,β problem by using the ability of adversary A to forge signature.
ℬ gives an example of SISq,n,m,β problem and uses the ability of A to give a solution.(1)
ℬ selects randomly matrix B in ℤqn×m(2)
ℬ finds a nonzero vector e∈ℤqm to make Be=O mod q and e≤β
First of all,ℬ creates three empty lists L1,L2,L3 to store the queries of adversary A, H2 and H4, and secret key. The interaction between ℬ and A is as follows:Setup: ℬ performs the following operations to generate the public parameter PP and all user identities UN and sends them to A.(1)
Determine the maximum possible user setUN=ID1,ID2,…,IDN and a challenge user IDi∗, i∗∈N(2)
Fori∈N, run Trapgenq,n,m to output a matrix H2IDi=Bi∈ℤqn×m together with a short basis TBi for Λ⊥Bi(3)
ℬ calls SampleMatpreBi∗,TBi∗,s,O and outputs D∈ℤqn×m and Bi∗D=O(4)
Randomly select matricesB,C in ℤqn×m. The user’s secret key is TBi∗ and his corresponding public key is PKi∗=B|Bi∗D∈ℤqn×2m(5)
Output public parametersPP=B,C,D and UN=ID1,ID2,…,IDNQuery: Adversary A can send the following query to ℬ, and ℬ will return the query result to A. For the identity subset U=IDi1,IDi2,…,IDil⊆UN, ℬ performs the following operations:Hash query 1:(1)
ℬ queries the list L1 first. If IDi has already been queried, ℬ returns H2IDi(2)
Otherwise, letH2IDi=Bi and Bi is sent to A. ℬ computes PKi=B|BiD, and add IDi,PKi,TBi to the list L1Hash query 2:(1)
A submits message μ to ℬ. For i∈l, ℬ randomly selects yi∈Ds12m. ℬ queries the list L2 and returns the same result if they already have been checked(2)
Otherwise,ℬ randomly selects v∈v∈ℤqm:v≤t and sends v to A and ℬ adds μ,U,y1,y2,…,yl,v to the list L2Extract query:A adaptively selects a user IDii∈N to ℬ. ℬ checks list L1 to find IDi,PKi,TBi and then uses IDi,PKi,TBi to run SampleMatprePKi,TBi,s,C. Output Si∈ℤq2m×m, satisfying PKiSi=C, and Si≤s2m. Add IDi,Si to the list L3.Sign query:A submits message μ, the identity subset U=IDi1,IDi2,…,IDil⊆UN, and the user IDit∈U to ℬ. ℬ operates as follows:(1)
ℬ checks the list L2. If μ,U,y1,y2,…,yl,v was not recorded, go to hash query 2 and record μ,U,y1,y2,…,yl,v in the list L2(2)
ℬ checks the list L3. If IDi,Si was not recorded, go to extract query and record IDi,Si in the list L3(3)
ℬ checks the lists L2 and L3. ℬ looks for the corresponding record μ,U,y1,y2,…,yl,v in L2 and the record IDi,Si in L3(4)
Letzj=yjj≠t and zj=Siv+yjj=t; ℬ returns the signature z1,z2,…,zl,v of the user IDitForgery:A submits message μ∗, the identity subset U∗=IDi1∗,IDi2∗,…,IDil∗⊆UN, and forged signature z1∗,z2∗,…,zl∗,v∗ by the user IDit∗∈U∗ to ℬ, meeting the following conditions:(1)
A has not asked for the private key of the user IDit∗(2)
A did not ask for U∗,μ∗’s signature
The signaturez1∗,z2∗,…,zl∗,v∗ is used in the following, which is an example of the identity subset U∗’s legal signature of message μ∗ to solve the SISq,n,m,β problem given at the beginning. ℬ first queries L2 to find μ∗,U∗,y1∗,y2∗,…,yl∗,v∗. If μ∗,U∗,y1∗,y2∗,…,yl∗,v∗ does not exist, then the game is terminated immediately. Otherwise, since z1∗,z2∗,…,zl∗,v∗ is a legal signature, we obtain(10)PKit∗zit∗−Cv∗=PKit∗yt∗.
ℬ extracts the key Sit∗ of IDit∗ in Table L3, and let zi′=yi∗ (if i≠t) and zit′=Sit∗v∗+yit∗(if i=t). It is easy to see that z1′,z2′,…,zl′,v∗ is also a legal signature, so(11)PKit∗zit′−Cv∗=PKit∗yt∗.
From (10) and (11), we obtain PKit∗zit∗−zit′=O.
Ifzit∗−zit′=O, then the game is terminated immediately.
Ifzit∗−zit′≠O, let zit∗−zit′=e,e′⊤, where e,e′∈ℤm. If e=O, then the game is terminated immediately. Otherwise, Be=O. Because PKit∗=B|H1IDit∗D and H1IDit∗D=O, it follows that PKit∗zit∗−zit′=Be|O=O; namely, Be=O. Because e≤zit∗−zit′≤zit∗+zit′≤2s12m, let β=2s12m; it is easy to check that e is the solution of the SISq,n,m,β problem that is put forward at the beginning.
In the following analysis,ℬ can successfully find the probability ϵ′ of e. ℬ will give up the game in the three following situations, which implies that the game fails.(1)
Whenμ∗,U∗,y1∗,y2∗,…,yl∗,v∗ is not in L2, the probability that v∗=H2∑i∈lPKizi−Cv∗,μ∗ passing the signature verification is 1/2t2m(2)
Whenzit∗−zit′=O, due to Δzit∗,Ds12m≤2−ωlog2m/M and Δzit′,Ds12m≤2−ωlog2m/M, Δzit∗,zit′≤Δzit∗,Ds12m+Δzit′,Ds12m≤22−ωlog2m/M(3)
Whene=O, namely, zit∗−zit′=O,e′⊤ and e′≠O, the statistical distance between zit∗ and zit′ satisfying Δzit∗,zit′≤82−ωlog2m/M
From the above analysis, we can see thatε′≥ϵ−1/2t2m−102−ωlog2m/M=ϵ−n−ω1.


## 6. Efficiency Analysis

In Table1, we set the following:PP: public parameters sizeMK: master key sizesk: secret key sizeσ: signature sizeTable 1
Comparison of communication costs.
SchemeReference [21], work-1Reference [21], work-2[22]This workPP5lm+k′nlogq2lmnlogq2mnlogq2l+3mnlogqMK2lm2logqlm2logqm2logql+1m2logqsk4lm2logq4lm2logqm2logq2l+1m2logqσ2lmlogq2lmlogqlm+1logq2lm+1logqFrom Table1, we may conclude that the communication and time cost of our scheme are larger than those of the scheme in [22], and only the size of private key is smaller than that of [21].In Table2, we set the following:Ext−Cost: secret key extraction costSig−Cost: signing costVer−Cost: verification costT1: the cost of RandBasis(ExtBasis)T2: the cost of Shamir’s secret sharing operationT3: the cost of SampleMatpreT4: the cost of SamplePreT5: the cost of matrix productT6: the cost of scalar multiplicationT7: the cost of BasisDelT8: the cost of matrix inversionTable 2
Comparison of time costs.
SchemeReference [21], work-1Reference [21], work-2[22]This workExt−CostlT1lT1T3+T5+T8l+1T1+T7Sig−CostnT2+lT4nT2+lT4ml+1T6mT1+lT3Ver−CostknT5+T6knT5+T6l+1T5Clk+l+1T5From Table2, we may conclude that our scheme has higher verification cost than those in [21, 22].


## 7. Conclusions

In this paper, we construct a fuzzy identity ring signature scheme based on SIS problem and prove its unforgeability in random oracle model. In particular, this scheme requires that the number of ring members be equal to the number of fuzzy identity coordinates. When the number of the components of the identity vector is greater than the number of the ring members, a certain number of temporary identities can be added as the ring members, so that the number of the ring members is equal to the number of the components of the identity vector. When the number of the ring members is more than the number of the components of the identity vector, a certain number of vector components will be randomly selected fromℤqm to expand the number of components of the identity vector. A signature issued under an identity ID can be verified by any identity ID′ that is “close enough” to the identity ID. This property allows our signature scheme to have an application in biometric authentication. Compared with the existing signature scheme of fuzzy identity, the scheme has the anonymity of ring signature which fuzzy identity signature does not have, so the efficiency of verification operation is lower. As the third step in the verification process, the worst case is to calculate Clk times, so when the signature scheme is used and Clk is too large in this paper, the verification efficiency will be very low. In the future, we hope to improve the algorithm of FIBRS to improve the efficiency of verification signature algorithm.



---

*Source: 6692608-2021-03-16.xml*