# Linkable Ring Signature Scheme Using Biometric Cryptosystem and NIZK and Its Application

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

---

## Abstract

Biometric encryption, especially based on fingerprint, plays an important role in privacy protection and identity authentication. In this paper, we construct a privacy-preserving linkable ring signature scheme. In our scheme, we utilize a fuzzy symmetric encryption scheme called symmetric keyring encryption (SKE) to hide the secret key and use non-interactive zero-knowledge (NIZK) protocol to ensure that we do not leak any information about the message. Unlike the blind signature, we use NIZK protocol to cancel the interaction between the signer (the prover) and the verifier. The security proof shows that our scheme is secure under the random oracle model. Finally, we implement it on a personal computer and analyze the performance of the constructed scheme in practical terms. Based on the constructed scheme and demo, we give an anonymous cryptocurrency transaction model as well as mobile demonstration.


---

## Body

## 1. Introduction

With the advantages of decentralized control and anonymous payment, cryptocurrency is gradually replacing the traditional payment mode. However, the anonymity provided by bitcoin has been questioned in the sense that it offers pseudonymity instead of real anonymity. The research work [1] has shown that attackers can improperly obtain the actual identity of a bitcoin’s owner or even other users through proxy addresses. In order to improve anonymity, researchers have proposed various privacy protection schemes, such as Dash based on the mixed coins protocol, Monero based on the CryptoNote protocol, and Zerocoin [2] based on the Zero-Knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARK) protocol [3], etc.In 2015, Noether [4] improved Monero’s original CryptoNote protocol by using a variant of linkable ring signature, which was called Ring Confidential Transactions (Ring CT). In the Ring CT protocol, Noether improved the “one-time ring signature” to linkable ring signature as the core cryptoprimitive to provide anonymity, which could not only meet the actual transaction needs, but also prevent the occurrence of double spending in transactions. Meanwhile, Monero also used stealth address to hide the recipient’s identity. Sasson et al. [2] proposed Zerocash, which used zk-SNARK protocol to construct the anonymous electronic cash system to protect the privacy of users and transaction amounts.Along with the development of cryptocurrency applications, privacy protection has gradually become an important issue. How to authenticate users while ensuring their anonymity has always been an important challenge in the information age. Biometric encryption technology which combines the cryptographic schemes with biometrics is an important branch of biometric protection technology. It is designed to protect secrets by binding/retrieving secrets with biometrics rather than using passwords or tokens in conventional cryptographic systems. Compared with passwords or tokens, biometrics such as fingerprints are more convenient, stable, and unforgettable. Nowadays, many biometric encryption algorithms have been proposed [5, 6]. In a word, combining biometric encryption technology and NIZK protocol with ring signatures will provide a great potential advantage for the protection of users’ privacy.


### 1.1. Related Work

Linkable Ring Signature Schemes. In 2004, linkability property was first introduced in a ring signature scheme by Liu et al. [7]. Later, Franklin and Zhang [8] proposed a general framework for linkable ring signatures. Nowadays, there were many variants of linkable ring signatures based on different features. Deng et al. [9] presented a new identity-based linkable ring signature scheme which avoided certificate management. Sun et al. [10] formalized the syntax of Ring CT protocol and then put forward a new efficient Ring CT protocol (Ring CT 2.0) which could save significant space.Non-Interactive Zero-Knowledge (NIZK) Protocol. In 1988, Blum et al. [11] firstly studied the NIZK proof system and presented the common reference string model which is generally applied to Zerocash. This construction is a NIZK range proof system based on a number theoretic assumption related to factoring. Using the Fiat-Shamir heuristic, Groth [12] suggested a NIZK argument for correctness of an approval vote. In order to optimize the size of NIZK proofs, Gentry et al. [13] constructed a fully homomorphic hybrid encryption scheme to minimize the communication cost. In 2019, Tsai et al. [14] proposed a new non-interactive ZKRP scheme to maintain high flexible range form.Biometric Encryption Schemes. In 1994, combining with fingerprint recognition, Tomoko firstly proposed the concept of biometric encryption and applied it for patents. Since then, various biometric cryptographic algorithms have been proposed. Juels and Sudan [15] put forward the concept of fuzzy vault whose security is based on the hardness of the polynomial reconstruction. However, Osadchy and Dunkelman [16] found that many of the existing schemes do not consider the privacy and security aspects of the feature extraction and binarization processes which have a huge risk for user privacy. Therefore, Lai et al. [5] proposed a novel biometric cryptosystem for vectorial biometrics called symmetric keyring encryption (SKE) by using an index of maximum hashed vectors, simple filtering mechanism, and Shamir’s secret-sharing scheme. They also formalized and analyzed the threat model for SKE, which involved four major security attacks.


### 1.2. Contributions

In this work, we firstly use a simplistic biometric secret-binding scheme called SKE to encrypt the secret key which can protect user’s secret key and authenticating user’s identity at the same time. Second, we utilize a NIZK protocol to provide anonymity for the message. Unlike the blind signatures [17, 18] which have similar property, no interaction is required during the signing and validation process of our scheme. The security analysis shows that our proposed scheme is provably secure under the random oracle model. Third, we analyze the performance of the proposed scheme and also implement it based on the fingerprint model. The encouraging results indicate that our scheme is practicable. Finally, we propose an anonymous cryptocurrency transaction model with a corresponding mobile demo.


### 1.3. Structure of the Paper

The rest of this paper is organized as follows. In Section2, some notations are introduced, and SKE and NIZK protocols are described. System framework and security model are presented in Section 3. We describe the signature scheme in Section 3. And its security analysis is provided in Section 5. In Section 6, some experimental results are given. The anonymous cryptocurrency transaction model is given in Section 7. Finally, the last section gives the conclusion.


## 1.1. Related Work

Linkable Ring Signature Schemes. In 2004, linkability property was first introduced in a ring signature scheme by Liu et al. [7]. Later, Franklin and Zhang [8] proposed a general framework for linkable ring signatures. Nowadays, there were many variants of linkable ring signatures based on different features. Deng et al. [9] presented a new identity-based linkable ring signature scheme which avoided certificate management. Sun et al. [10] formalized the syntax of Ring CT protocol and then put forward a new efficient Ring CT protocol (Ring CT 2.0) which could save significant space.Non-Interactive Zero-Knowledge (NIZK) Protocol. In 1988, Blum et al. [11] firstly studied the NIZK proof system and presented the common reference string model which is generally applied to Zerocash. This construction is a NIZK range proof system based on a number theoretic assumption related to factoring. Using the Fiat-Shamir heuristic, Groth [12] suggested a NIZK argument for correctness of an approval vote. In order to optimize the size of NIZK proofs, Gentry et al. [13] constructed a fully homomorphic hybrid encryption scheme to minimize the communication cost. In 2019, Tsai et al. [14] proposed a new non-interactive ZKRP scheme to maintain high flexible range form.Biometric Encryption Schemes. In 1994, combining with fingerprint recognition, Tomoko firstly proposed the concept of biometric encryption and applied it for patents. Since then, various biometric cryptographic algorithms have been proposed. Juels and Sudan [15] put forward the concept of fuzzy vault whose security is based on the hardness of the polynomial reconstruction. However, Osadchy and Dunkelman [16] found that many of the existing schemes do not consider the privacy and security aspects of the feature extraction and binarization processes which have a huge risk for user privacy. Therefore, Lai et al. [5] proposed a novel biometric cryptosystem for vectorial biometrics called symmetric keyring encryption (SKE) by using an index of maximum hashed vectors, simple filtering mechanism, and Shamir’s secret-sharing scheme. They also formalized and analyzed the threat model for SKE, which involved four major security attacks.


## 1.2. Contributions

In this work, we firstly use a simplistic biometric secret-binding scheme called SKE to encrypt the secret key which can protect user’s secret key and authenticating user’s identity at the same time. Second, we utilize a NIZK protocol to provide anonymity for the message. Unlike the blind signatures [17, 18] which have similar property, no interaction is required during the signing and validation process of our scheme. The security analysis shows that our proposed scheme is provably secure under the random oracle model. Third, we analyze the performance of the proposed scheme and also implement it based on the fingerprint model. The encouraging results indicate that our scheme is practicable. Finally, we propose an anonymous cryptocurrency transaction model with a corresponding mobile demo.


## 1.3. Structure of the Paper

The rest of this paper is organized as follows. In Section2, some notations are introduced, and SKE and NIZK protocols are described. System framework and security model are presented in Section 3. We describe the signature scheme in Section 3. And its security analysis is provided in Section 5. In Section 6, some experimental results are given. The anonymous cryptocurrency transaction model is given in Section 7. Finally, the last section gives the conclusion.


## 2. Preliminary

First, we give some notations in Table1 which are used in the rest of this paper.Table 1
Notations.
SymbolRepresentationG,GTCyclic group or prime of prime orderqℤqRing of integers moduloqℤq∗ℤq/0Gn,ℤqnVector spaces of dimensionn over G and ZqeEfficiently computable nondegenerate pairingG×G⟶GTℝdContinuous domainN1,…,NεlThe negligible functionπ^Omitting the indexπYRandom projection matrix composed ofq Gaussian row vectorsNRandom projection matrixY1,…,YmφxiargmaxiYi where i∈0,1,…,qH1,H2,H3A hash function returning a value inℤqHpA map-to-point hash function


### 2.1. SKE Model

The SKE model is a novel simplistic biometric secret-binding scheme for vectorial biometrics which is based on the notion of symmetric key cryptosystems [5]. First, the SKE model uses IoM hashing [19] which can generate abundant IoM hashed entries as genuine entries without being restricted by the original biometric vector size. We use x∈ℤqd as an enrolled biometric vector and N as a random projection matrix. Given x,m,N, the IoM hashing operations as follows: ΩIoMx,m,N⟶ϕx∈ℤqm.During enrollment, there is a user with an enrolled biometric vectorx, parameter m, two different nonces N, N^, and a finite field polynomial f⋅∈ℱqm of order to generate ϕx and φ^x. Then, we perform polynomial projection to generate fϕx and yield a public secure sketch ss=φ^x1⊕fφx1,…,φ^xm⊕fφxm. Finally, we generate authentication tag TAG=tag1,…,tagm, where tagi=Hφxissiφ^xi is the one-way hashed output. We store N,N^,TAG,ss as the public helper data.During secret retrieval, given the query biometric vectorx′ and the public helper data above, we generate ϕx′ and φ^x′ as well as tagi′ and TAG′ following the steps above.Whentagi′=tagi, we can get a genuine pair φxi,fφxi∈G, where G is a genuine set. If we have a sufficient number of revealed genuine pairs with U=t≥k, the secret key y can be retrieved via polynomial interpolation using the unlocking set U=φxi,fφxii=1t. A high-level overview of SKE is shown in Figure 1.Figure 1
The process of SKE.


### 2.2. NIZK Protocol

NIZK protocols can be used to demonstrate the truth of a statement without revealing anything else. We briefly state the NIZK protocol [12] which we will use below. First, we set the system parameters g,h∈G. We also denote H1⋅, H2⋅ to be secure hash functions and individually output μ,e∈ℤq. Randomizer R and message are prover’s input. Then, we simply discuss this NIZK as follows.(i)
Argument:(1)
ComputeH1message=μ and C=μg+Rh∈G.(2)
Randomly chooseRμ,RR∈ℤq∗; compute CR=Rμg+RRh and e=H2C,CR.(3)
Setμ′=eμ+Rμ, R′=eR+RR.(4)
The argument isCR,μ′,R′.(ii)
Verifier:(1)
Computee as above.(2)
Verify whethereC+CR=μ′g+R′h.In this instance, it is easy to see that prover can convince the verifier that he/she knowsmessage without revealing knowledge message and interacting with the verifier.NIZK proofs are usually use in the common reference string (CRS) model, where in a string of a special structure is generated in a setup phase and made available for everyone to prove/verify statements.Definition 1 (NIZK Argument [20]).
A NIZK argument for an NP relationRconsists of a triple of polynomial time algorithmsSetup,Prove,Verifydefined as follows:(1)
Setup1κ takes a security parameter κ and outputs a CRS Σ.(2)
ProveΣ,s,w takes as input the CRS Σ, a statement s, and a witness w and outputs an argument π.(3)
VerifyΣ,s,π takes as input the CRS Σ, a statement s, and a proof π and outputs either 1 accepting the argument or 0 rejecting it.
The algorithms above should satisfy the following three properties.(1)
Completeness. For allκ∈ℕ, s,w∈R, PrVerifyΣ,s,w=1=1.(2)
Computational soundness. For allPPT adversaries A, the following probability is negligible in κ:(1)PrVerifyΣ,s˜,w˜=1∧s˜∉L.(3)
Zero-knowledge. There exists aPPT simulator C1,C2 such that C1 outputs a simulated CRS Σ and trapdoor τ; C2 takes as input Σ, a statement s and τ and outputs a simulated proof π′; and, for all PPT adversaries A1,A2, the following probability is negligible in κ:(2)Prs,w∈R∧A2π,st=1−Prs,w∈R∧A2π′,st=1.Definition 2 (NIZK Argument of Knowledge [20]).
A NIZK argument of knowledge for a relationR is a NIZK argument for R with the following additional extractability property.
(1) Extraction. For any PPT adversary A, random string r⟵0,1∗, there exists a PPT algorithm Ext outputting w′ such that the following probability is negligible in κ:(3)PrVerifyΣ,s˜,π˜=1∧Rs˜,w′=0.


### 2.3. (t, u)-Threshold Secret-Sharing Scheme

In this section, we describe a (t, u)-threshold scheme [21] which enables making u shares (distribution) and recovering the secret from t or more shares (recovery) using just XOR operations, for arbitrary threshold t and the number of participants u. We will only use the distribution algorithm which is described in Algorithm 1. In this algorithm, the secret y∈0,1dup−1 needs to be divided equally into up−1 blocks y1,…,yup−1∈0,1d, where up is a prime number, and d>0 denotes the bit-size of every divided piece of the secret. Also, it uses u shares, y1,…,yu, of a t,up-threshold scheme to construct a (t, u)-threshold scheme if the desired number of participants u is a composite number (in our scheme, we set u=up).Algorithm 1: DisThreshold (y, t, u).
Input:y∈0,1dup−1.Output:y=y1,…,yu(1)
s=0d, s1⋯sup−1=s.(2)
for1≤i≤t−1 do(3)
for1≤j≤up do(4)
Chooserji=GEN0,1d;(5)
end(6)
end(7)
for1≤i≤u do(8)
for1≤j≤up−1 do(9)
Chooseyi,j=⊕h=1t−1rh⋅i+jh⊕sj−i;(10)
end(11)
yi=yi,1⋯yi,up−1(12)
end(13)
returny=y1,…,yu.These XORed terms are circulated in a specific pattern witht dimensions and do not overlap with each other because the properties of prime numbers are used. By an implementation on a PC, they showed that the proposed scheme is able to make u shares from the secret and recover the secret from t shares more quickly than Shamir’s scheme [22] if u is not extremely large.


### 2.4. UTXO Ledger Model

Bitcoin, the most valuable and popular cryptocurrency, uses a graph-based ledger model built on the concept of UTXOs (unspent transaction outputs). In the UTXO ledger model, individual transactions consist of a list of inputs and a list of outputs. Each of the transactions can merge the bitcoins in the previous multiple accounts and transfer them to another one or more accounts. Figure2 shows how UTXO model works, where Tx1 contains one input and two outputs, and Tx2 contains three inputs and two outputs.Figure 2
UTXO ledger model.


### 2.5. Linkable Ring Signature

The biometric cryptosystem can be found in [5] and the NIZK scheme can be found in [12]. Our definitions are in the spirit of [4, 5, 12].Definition 3.
A linkable ring signature scheme based on SKE and NIZK consists of five algorithms:(1)
Setup: on input of the user’s biometric vectorxand a finite field polynomial orderk−1, output public helper dataPP.(2)
KeyGen: on input of the user’s biometric vectorx′and public helper dataPP, output the secret key-vectorsyand its corresponding public key-vectorsPK.(3)
Sign: on input of a message, the parametersg,h,R,G, and the setL=PKiji∈nj∈uwhereyj,PKπjis a valid key pair output byKeyGenandPKπj∈L, output a signatureΩ.(4)
Verify: on input of the purported signaturesΩ, anyone can verifyΩand output a bitb∈0,1.(5)
Link: on input of two messagesM1,M2as well as two signaturesΩ1andΩ2, output a bitb∈0,1.


### 2.6. Complexity Assumptions and Lemma

Definition 4 (Discrete Logarithm (DL) Assumption).
Given a generatorgofG∗, whereG∗=GorGT, anda∈ℤq∗, for every adversaryA,PrAg,ag=a=εκ.Definition 5 (Decision Diffie-Hellman (DDH) Assumption).
Distinguish the distributionsag,bg,abgandag,bg,cgwitha,b,c⟵ℤqandg∈G. The DDH assumption is the intractability of the problem for anyPPTdistinguisher.Lemma 1 (From Liu et al. [7]).
LetAbe an attacker andCbe a challenger;CinvokesAto obtain a transcriptT; ifTis successful, thenCrewindsTto a headerℌand resimulatesAto obtain transcriptT′. If PrTsucceeds=ε, then PrT′succeeds=ε.


## 2.1. SKE Model

The SKE model is a novel simplistic biometric secret-binding scheme for vectorial biometrics which is based on the notion of symmetric key cryptosystems [5]. First, the SKE model uses IoM hashing [19] which can generate abundant IoM hashed entries as genuine entries without being restricted by the original biometric vector size. We use x∈ℤqd as an enrolled biometric vector and N as a random projection matrix. Given x,m,N, the IoM hashing operations as follows: ΩIoMx,m,N⟶ϕx∈ℤqm.During enrollment, there is a user with an enrolled biometric vectorx, parameter m, two different nonces N, N^, and a finite field polynomial f⋅∈ℱqm of order to generate ϕx and φ^x. Then, we perform polynomial projection to generate fϕx and yield a public secure sketch ss=φ^x1⊕fφx1,…,φ^xm⊕fφxm. Finally, we generate authentication tag TAG=tag1,…,tagm, where tagi=Hφxissiφ^xi is the one-way hashed output. We store N,N^,TAG,ss as the public helper data.During secret retrieval, given the query biometric vectorx′ and the public helper data above, we generate ϕx′ and φ^x′ as well as tagi′ and TAG′ following the steps above.Whentagi′=tagi, we can get a genuine pair φxi,fφxi∈G, where G is a genuine set. If we have a sufficient number of revealed genuine pairs with U=t≥k, the secret key y can be retrieved via polynomial interpolation using the unlocking set U=φxi,fφxii=1t. A high-level overview of SKE is shown in Figure 1.Figure 1
The process of SKE.


## 2.2. NIZK Protocol

NIZK protocols can be used to demonstrate the truth of a statement without revealing anything else. We briefly state the NIZK protocol [12] which we will use below. First, we set the system parameters g,h∈G. We also denote H1⋅, H2⋅ to be secure hash functions and individually output μ,e∈ℤq. Randomizer R and message are prover’s input. Then, we simply discuss this NIZK as follows.(i)
Argument:(1)
ComputeH1message=μ and C=μg+Rh∈G.(2)
Randomly chooseRμ,RR∈ℤq∗; compute CR=Rμg+RRh and e=H2C,CR.(3)
Setμ′=eμ+Rμ, R′=eR+RR.(4)
The argument isCR,μ′,R′.(ii)
Verifier:(1)
Computee as above.(2)
Verify whethereC+CR=μ′g+R′h.In this instance, it is easy to see that prover can convince the verifier that he/she knowsmessage without revealing knowledge message and interacting with the verifier.NIZK proofs are usually use in the common reference string (CRS) model, where in a string of a special structure is generated in a setup phase and made available for everyone to prove/verify statements.Definition 1 (NIZK Argument [20]).
A NIZK argument for an NP relationRconsists of a triple of polynomial time algorithmsSetup,Prove,Verifydefined as follows:(1)
Setup1κ takes a security parameter κ and outputs a CRS Σ.(2)
ProveΣ,s,w takes as input the CRS Σ, a statement s, and a witness w and outputs an argument π.(3)
VerifyΣ,s,π takes as input the CRS Σ, a statement s, and a proof π and outputs either 1 accepting the argument or 0 rejecting it.
The algorithms above should satisfy the following three properties.(1)
Completeness. For allκ∈ℕ, s,w∈R, PrVerifyΣ,s,w=1=1.(2)
Computational soundness. For allPPT adversaries A, the following probability is negligible in κ:(1)PrVerifyΣ,s˜,w˜=1∧s˜∉L.(3)
Zero-knowledge. There exists aPPT simulator C1,C2 such that C1 outputs a simulated CRS Σ and trapdoor τ; C2 takes as input Σ, a statement s and τ and outputs a simulated proof π′; and, for all PPT adversaries A1,A2, the following probability is negligible in κ:(2)Prs,w∈R∧A2π,st=1−Prs,w∈R∧A2π′,st=1.Definition 2 (NIZK Argument of Knowledge [20]).
A NIZK argument of knowledge for a relationR is a NIZK argument for R with the following additional extractability property.
(1) Extraction. For any PPT adversary A, random string r⟵0,1∗, there exists a PPT algorithm Ext outputting w′ such that the following probability is negligible in κ:(3)PrVerifyΣ,s˜,π˜=1∧Rs˜,w′=0.


## 2.3. (t, u)-Threshold Secret-Sharing Scheme

In this section, we describe a (t, u)-threshold scheme [21] which enables making u shares (distribution) and recovering the secret from t or more shares (recovery) using just XOR operations, for arbitrary threshold t and the number of participants u. We will only use the distribution algorithm which is described in Algorithm 1. In this algorithm, the secret y∈0,1dup−1 needs to be divided equally into up−1 blocks y1,…,yup−1∈0,1d, where up is a prime number, and d>0 denotes the bit-size of every divided piece of the secret. Also, it uses u shares, y1,…,yu, of a t,up-threshold scheme to construct a (t, u)-threshold scheme if the desired number of participants u is a composite number (in our scheme, we set u=up).Algorithm 1: DisThreshold (y, t, u).
Input:y∈0,1dup−1.Output:y=y1,…,yu(1)
s=0d, s1⋯sup−1=s.(2)
for1≤i≤t−1 do(3)
for1≤j≤up do(4)
Chooserji=GEN0,1d;(5)
end(6)
end(7)
for1≤i≤u do(8)
for1≤j≤up−1 do(9)
Chooseyi,j=⊕h=1t−1rh⋅i+jh⊕sj−i;(10)
end(11)
yi=yi,1⋯yi,up−1(12)
end(13)
returny=y1,…,yu.These XORed terms are circulated in a specific pattern witht dimensions and do not overlap with each other because the properties of prime numbers are used. By an implementation on a PC, they showed that the proposed scheme is able to make u shares from the secret and recover the secret from t shares more quickly than Shamir’s scheme [22] if u is not extremely large.


## 2.4. UTXO Ledger Model

Bitcoin, the most valuable and popular cryptocurrency, uses a graph-based ledger model built on the concept of UTXOs (unspent transaction outputs). In the UTXO ledger model, individual transactions consist of a list of inputs and a list of outputs. Each of the transactions can merge the bitcoins in the previous multiple accounts and transfer them to another one or more accounts. Figure2 shows how UTXO model works, where Tx1 contains one input and two outputs, and Tx2 contains three inputs and two outputs.Figure 2
UTXO ledger model.


## 2.5. Linkable Ring Signature

The biometric cryptosystem can be found in [5] and the NIZK scheme can be found in [12]. Our definitions are in the spirit of [4, 5, 12].Definition 3.
A linkable ring signature scheme based on SKE and NIZK consists of five algorithms:(1)
Setup: on input of the user’s biometric vectorxand a finite field polynomial orderk−1, output public helper dataPP.(2)
KeyGen: on input of the user’s biometric vectorx′and public helper dataPP, output the secret key-vectorsyand its corresponding public key-vectorsPK.(3)
Sign: on input of a message, the parametersg,h,R,G, and the setL=PKiji∈nj∈uwhereyj,PKπjis a valid key pair output byKeyGenandPKπj∈L, output a signatureΩ.(4)
Verify: on input of the purported signaturesΩ, anyone can verifyΩand output a bitb∈0,1.(5)
Link: on input of two messagesM1,M2as well as two signaturesΩ1andΩ2, output a bitb∈0,1.


## 2.6. Complexity Assumptions and Lemma

Definition 4 (Discrete Logarithm (DL) Assumption).
Given a generatorgofG∗, whereG∗=GorGT, anda∈ℤq∗, for every adversaryA,PrAg,ag=a=εκ.Definition 5 (Decision Diffie-Hellman (DDH) Assumption).
Distinguish the distributionsag,bg,abgandag,bg,cgwitha,b,c⟵ℤqandg∈G. The DDH assumption is the intractability of the problem for anyPPTdistinguisher.Lemma 1 (From Liu et al. [7]).
LetAbe an attacker andCbe a challenger;CinvokesAto obtain a transcriptT; ifTis successful, thenCrewindsTto a headerℌand resimulatesAto obtain transcriptT′. If PrTsucceeds=ε, then PrT′succeeds=ε.


## 3. Security Model

In consideration of the security, our scheme should satisfy four fundamental properties: unforgeability, anonymity, linkability, and zero-knowledge which are very similar to the definitions given by [4, 7].Before giving the definition, we give the definitions of the following queries at first. They will be carried out between a challengerC and an adversary A, which together simulate the ability of the adversary.(1)
Hash functions query:A may request the values of the hash functions for any input.(2)
Key query:A requests the key of a user; C responds with the secret key.(3)
Signature query:A submits a tuple M,x,L; C outputs a signature.


### 3.1. Unforgeability

We give the adversary model about unforgeability, which follows a similar structure as [4, 7].For any PPT adversaryA, the advantage that A wins the following game can be ignored; then our scheme is said to be unforgeable.Game I: an adversary A plays a game with a challenger C as follows.Initialization: running the Setup algorithm, C obtains the public helper data PP and then gives it to A.Query:A performs a polynomially bounded number of queries.Forge:A submits a new tuple Ω∗,x∗,M∗,L∗. A will win if the following conditions hold:(1)
Ω∗ is a legal signature.(2)
A did not query the key of anyone in L∗.(3)
A did not query the tuple x∗,M∗.The advantage of the unforgeability is denoted by(4)AdvantageAForge=PrAsucceeds.If for anyPPT algorithm A, the advantage of AdvantageAForge is negligible, we say the scheme is unforgeable.


### 3.2. Anonymity

Our scheme is said to be signer anonymity if for anyPPT adversary A, AdvantageAForge is negligible.Game II: an adversary A plays a game with a challenger C as follows.Initialization: it is the same as that in Game I.Query:A performs a polynomially bounded number of queries.Challenge:A outputs a new tuple M,xi,0,xi,1,L. C flips a coin b∈0,1 and then returns A with the signature ΩM,xi,b,L.Guess:A outputs a bit b′. If b=b′, A is considered to succeed with the probability of SuccessAAnon.The anonymity advantage of our scheme is denoted byAdvantageAAnon=SuccessAAnon−1/2.


### 3.3. Linkability

If for anyPPT adversary A, the advantage of A is ignorable in the following game, our scheme is said to be linkable.Game III: an adversary A plays a game with a challenger C as follows.Initialization, Query: it is the same as that in Game I.Unlink:A outputs two valid signatures Ω1,M1,L1 and Ω2,M2,L2 with respect to secret keys y1 and y2, respectively. A wins if the following conditions hold:(1)
VerifyΩ1,M1,L1= Verify Ω2,M2,L2=1.(2)
y1∩y2≠∅.(3)
LinkΩ1,Ω2= unlink.The advantage of the linkability is denoted byAdvantageALink=PrAwins.


### 3.4. NIZK Argument

In ROM, if our scheme is proved to be completeness, computational soundness, and zero-knowledge, our protocol is a NIZK argument where the plaintext space isℤq.


## 3.1. Unforgeability

We give the adversary model about unforgeability, which follows a similar structure as [4, 7].For any PPT adversaryA, the advantage that A wins the following game can be ignored; then our scheme is said to be unforgeable.Game I: an adversary A plays a game with a challenger C as follows.Initialization: running the Setup algorithm, C obtains the public helper data PP and then gives it to A.Query:A performs a polynomially bounded number of queries.Forge:A submits a new tuple Ω∗,x∗,M∗,L∗. A will win if the following conditions hold:(1)
Ω∗ is a legal signature.(2)
A did not query the key of anyone in L∗.(3)
A did not query the tuple x∗,M∗.The advantage of the unforgeability is denoted by(4)AdvantageAForge=PrAsucceeds.If for anyPPT algorithm A, the advantage of AdvantageAForge is negligible, we say the scheme is unforgeable.


## 3.2. Anonymity

Our scheme is said to be signer anonymity if for anyPPT adversary A, AdvantageAForge is negligible.Game II: an adversary A plays a game with a challenger C as follows.Initialization: it is the same as that in Game I.Query:A performs a polynomially bounded number of queries.Challenge:A outputs a new tuple M,xi,0,xi,1,L. C flips a coin b∈0,1 and then returns A with the signature ΩM,xi,b,L.Guess:A outputs a bit b′. If b=b′, A is considered to succeed with the probability of SuccessAAnon.The anonymity advantage of our scheme is denoted byAdvantageAAnon=SuccessAAnon−1/2.


## 3.3. Linkability

If for anyPPT adversary A, the advantage of A is ignorable in the following game, our scheme is said to be linkable.Game III: an adversary A plays a game with a challenger C as follows.Initialization, Query: it is the same as that in Game I.Unlink:A outputs two valid signatures Ω1,M1,L1 and Ω2,M2,L2 with respect to secret keys y1 and y2, respectively. A wins if the following conditions hold:(1)
VerifyΩ1,M1,L1= Verify Ω2,M2,L2=1.(2)
y1∩y2≠∅.(3)
LinkΩ1,Ω2= unlink.The advantage of the linkability is denoted byAdvantageALink=PrAwins.


## 3.4. NIZK Argument

In ROM, if our scheme is proved to be completeness, computational soundness, and zero-knowledge, our protocol is a NIZK argument where the plaintext space isℤq.


## 4. Signature Scheme

### 4.1. Our Construction

The detailed steps of our scheme are given as follows.Setup. xOn input ofx∈ℤqd, two random nonces N,N^∈ℤqmq×d, parameter m∈ℤq, a finite field polynomial f⋅ which encodes the secret key y, and a one-way hash function H:0,1∗⟶0,1l, the Setup algorithm does as follows:(1)
Run IoMx to generate vectors φx⟵ΩIoMx,m,N and φ^x⟵ΩIoMx,m,N^, where φx=φx1,…,φxm, φ^x=φ^x1,…,φ^xm.(2)
Computefφx=fφx1,…,fφxm.(3)
Fori∈m, compute ssi=φ^xi⊕fφxi, such that the secure sketch ss=s1,…,sm.(4)
Fori∈m, compute tagi=Hφxissiφ^xi, such that TAG=tag1,…,tagm.(5)
Output the public helper dataPP=N,N^,ss,TAG.A formal description of this algorithm is shown Algorithm2.Algorithm 2: Setup x.
Input:x, m, f⋅, N, N^Output:PP = {N, N^, ss, TAG}(1)
Letφx=ΩIoMx,m,N, φ^x=ΩIoMx,m,N^.(2)
Callf⋅ to obtain(3)
fφx=fφx1,…,fφxm.(4)
for1≤i≤m do(5)
Computessi=φ^xi⊕fφxi,(6)
tagi=Hφxissiφ^xi.(7)
end(8)
Letss=s1,…,sm, TAG=tag1,…,tagm.(9)
returnPP = {N, N^, ss, TAG}.KeyGen.x′On inputx′∈ℤqd, u∈ℤq, the public helper data PP=N,N^,ss,TAG with parameter m, generator G∈G, and the set U=∅. The KeyGen algorithm does as follows:(1)
RunIoMx′ to generate vectors φx′⟵ΩIoMx′,m,N and φ^x′⟵ΩIoMx′,m,N^∈ℱqm.(2)
Fori∈m, compute tagi′=Hφx′issiφ^x′i, such that TAG′=tag1′,…,tagm′.(3)
Fori∈m, compute fφxi′=ssi⊕φ^x′i while tagi′=tagi, and then add φxi,fφxi′ to an unlocking set U.(4)
IfU≥k, perform polynomial reconstruction with U and output the secret key y=f0∈ℤq∗; else repeat step 1.(5)
Run DisThreshold (y, u−1, u) to obtain y, output y=y1,…,yu.(6)
Forj∈u, compute PKi=yiG∈G. The PK=PK1,…,PKu and y are the public key-vectors and the secret key-vectors, respectively.A formal description of this algorithm is shown as Algorithm3.Algorithm 3: KeyGen x′.
Input:x′, u, m, G, U, PP=N,N^,ss,TAG.Output:PK.(1)
Computeφx′=ΩIoMx′,m,N, φ^x′=ΩIoMx′,m,N^.(2)
LetU=∅.(3)
for1≤i≤m do(4)
Computetagi′=Hφx′issiφ^x′i.(5)
iftagi′==tagi then(6)
Computefφxi′=ssi⊕φ^x′i(7)
ifφxi,fφxi′∉U then(8)
LetU=U∪φxi,fφxi′(9)
end(10)
end(11)
end(12)
Lett=U.(13)
ift≥k then(14)
Call functionlagrange⋅0 to obtain y(15)
RunDisThresholdy,u−1,u to obtain y(16)
for1≤i≤u do(17)
ComputePKi=yiG.(18)
end(19)
end(20)
returnPK=PK1,…,PKu, y.Sign.On input themessage∈0,1l, generators g,h,G∈G, R∈ℤq∗, and public key-matrix L=PK1,…,PKnPKi=PKi1,…,PKiu containing n public key-vectors of length u, user’s secret key y corresponding to PKπ. We do as follows:(1)
LetH1message=μ, choose Rμ,RR⟵ℤq∗, compute C=μg+Rh; CR=Rμg+RRh; e=H2C,CR.(2)
ComputeM=eμ+Rμ, R′=eR+RR.(3)
Forj∈u, i=1,…,π^,…,n, choose sij⟵ℤq; when i=π, choose aπj⟵ℤq.(4)
Forj∈u, compute the key image Ij=yjHpPKπj∈G.(5)
Wheni=π, for j∈u, compute Lπj=aπjG; Rπj=aπjHpPKπj;cπ+1=H3M,Lπ1,Rπ1,…,Lπu,Rπu.(6)
Wheni=π+1,…,n,1,…,π−1, for j∈u, compute Lij=sijG+ciPKij; Rij=sijHpPKij+ciIj; ci+1=H3M,Li1,Ri1,…,Liu,Riu.(7)
Wheni=π, for j∈u, compute sπj=aj−cπyjmodq.(8)
OutputΩM=Ij,c1,sij,CR,M,R′i∈n,j∈u.A formal description of this algorithm is shown as Algorithm4.Algorithm 4: Sign (message, L, y).
Input:message∈0,1l, g,h,G∈G, R∈ℤq∗, L=PK1,…,PKnPKi=PKi1,…,PKiu, y.Output:ΩM=Ij,c1,sij,CR,M,R′i∈n,j∈u.(1)
LetH1message=μ.(2)
ComputeC=μg+Rh, CR=Rμg+RRh and e=H2C,CR where(3)
Rμ,RR⟶ℤq∗.(4)
ComputeM=eμ+Rμ, R′=eR+RR.(5)
for1≤j≤u do(6)
Chooseaπj←ℤq(7)
ComputeIj=yjHpPKπj; Lπj=aπjG;(8)
Rπj=aπjHpPKπj;(9)
end(10)
Computecπ+1=H3M,Lπ1,Rπ1,…,Lπu,Rπu.(11)
fori=π+1,…,n,1,…,π−1 do(12)
for1≤j≤u do(13)
Choosesij←ℤq(14)
ComputeLij=sijG+ciPKij;(15)
Rij=sijHpPKij+ciIj;(16)
end(17)
Computeci+1=H3M,Li1,Ri1,…,Liu,Riu;(18)
end(19)
for1≤j≤u do(20)
Computesπj=aj−cπyjmodq;(21)
end(22)
returnΩM=Ij,c1,sij,CR,M,R′i∈n,j∈u.Verify(1)
The verifier computese=H2C,CR. Then, checking whether eC+CR=Mg+R′h. If the congruence holds, return ″1″, otherwise ″0″.(2)
Fori∈n,j∈u, the verifier regenerates all the Lij,Rij,ci+1 and verifies whether cn+1=c1. If the congruence holds, return ″1″, otherwise ″0″.A formal description of this algorithm is shown Algorithm5.Algorithm 5: Verify(Ω, L).
Input:ΩM=Ij,c1,sij,CR,M,R′i∈n,j∈u,g,h∈G, L=PK1,…,PKnPKi=PKi1,…,PKiu.Output: 0 or 1.(1)
Computee=H2C,CR.(2)
ifeC+CR=Mg+R′h then(3)
for1≤i≤n do(4)
for1≤j≤u do(5)
ComputeLij=sijG+ciPKij;(6)
Rij=sijHpPKij+ciIj(7)
end(8)
Computeci+1=H3M,Li1,Ri1,…,Liu,Riu;(9)
end(10)
else(11)
0(12)
end(13)
ifcn+1=c1 then 1;(14)
else 0;(15)
return 0 or 1.Link.For a fixed set of public key-vectors, given two messagesM,M′, two valid signatures ΩM and Ω′M′, the verifier outputs link if the key image Ij=Ij′j∈u; otherwise the verifier outputs unlink.


## 4.1. Our Construction

The detailed steps of our scheme are given as follows.Setup. xOn input ofx∈ℤqd, two random nonces N,N^∈ℤqmq×d, parameter m∈ℤq, a finite field polynomial f⋅ which encodes the secret key y, and a one-way hash function H:0,1∗⟶0,1l, the Setup algorithm does as follows:(1)
Run IoMx to generate vectors φx⟵ΩIoMx,m,N and φ^x⟵ΩIoMx,m,N^, where φx=φx1,…,φxm, φ^x=φ^x1,…,φ^xm.(2)
Computefφx=fφx1,…,fφxm.(3)
Fori∈m, compute ssi=φ^xi⊕fφxi, such that the secure sketch ss=s1,…,sm.(4)
Fori∈m, compute tagi=Hφxissiφ^xi, such that TAG=tag1,…,tagm.(5)
Output the public helper dataPP=N,N^,ss,TAG.A formal description of this algorithm is shown Algorithm2.Algorithm 2: Setup x.
Input:x, m, f⋅, N, N^Output:PP = {N, N^, ss, TAG}(1)
Letφx=ΩIoMx,m,N, φ^x=ΩIoMx,m,N^.(2)
Callf⋅ to obtain(3)
fφx=fφx1,…,fφxm.(4)
for1≤i≤m do(5)
Computessi=φ^xi⊕fφxi,(6)
tagi=Hφxissiφ^xi.(7)
end(8)
Letss=s1,…,sm, TAG=tag1,…,tagm.(9)
returnPP = {N, N^, ss, TAG}.KeyGen.x′On inputx′∈ℤqd, u∈ℤq, the public helper data PP=N,N^,ss,TAG with parameter m, generator G∈G, and the set U=∅. The KeyGen algorithm does as follows:(1)
RunIoMx′ to generate vectors φx′⟵ΩIoMx′,m,N and φ^x′⟵ΩIoMx′,m,N^∈ℱqm.(2)
Fori∈m, compute tagi′=Hφx′issiφ^x′i, such that TAG′=tag1′,…,tagm′.(3)
Fori∈m, compute fφxi′=ssi⊕φ^x′i while tagi′=tagi, and then add φxi,fφxi′ to an unlocking set U.(4)
IfU≥k, perform polynomial reconstruction with U and output the secret key y=f0∈ℤq∗; else repeat step 1.(5)
Run DisThreshold (y, u−1, u) to obtain y, output y=y1,…,yu.(6)
Forj∈u, compute PKi=yiG∈G. The PK=PK1,…,PKu and y are the public key-vectors and the secret key-vectors, respectively.A formal description of this algorithm is shown as Algorithm3.Algorithm 3: KeyGen x′.
Input:x′, u, m, G, U, PP=N,N^,ss,TAG.Output:PK.(1)
Computeφx′=ΩIoMx′,m,N, φ^x′=ΩIoMx′,m,N^.(2)
LetU=∅.(3)
for1≤i≤m do(4)
Computetagi′=Hφx′issiφ^x′i.(5)
iftagi′==tagi then(6)
Computefφxi′=ssi⊕φ^x′i(7)
ifφxi,fφxi′∉U then(8)
LetU=U∪φxi,fφxi′(9)
end(10)
end(11)
end(12)
Lett=U.(13)
ift≥k then(14)
Call functionlagrange⋅0 to obtain y(15)
RunDisThresholdy,u−1,u to obtain y(16)
for1≤i≤u do(17)
ComputePKi=yiG.(18)
end(19)
end(20)
returnPK=PK1,…,PKu, y.Sign.On input themessage∈0,1l, generators g,h,G∈G, R∈ℤq∗, and public key-matrix L=PK1,…,PKnPKi=PKi1,…,PKiu containing n public key-vectors of length u, user’s secret key y corresponding to PKπ. We do as follows:(1)
LetH1message=μ, choose Rμ,RR⟵ℤq∗, compute C=μg+Rh; CR=Rμg+RRh; e=H2C,CR.(2)
ComputeM=eμ+Rμ, R′=eR+RR.(3)
Forj∈u, i=1,…,π^,…,n, choose sij⟵ℤq; when i=π, choose aπj⟵ℤq.(4)
Forj∈u, compute the key image Ij=yjHpPKπj∈G.(5)
Wheni=π, for j∈u, compute Lπj=aπjG; Rπj=aπjHpPKπj;cπ+1=H3M,Lπ1,Rπ1,…,Lπu,Rπu.(6)
Wheni=π+1,…,n,1,…,π−1, for j∈u, compute Lij=sijG+ciPKij; Rij=sijHpPKij+ciIj; ci+1=H3M,Li1,Ri1,…,Liu,Riu.(7)
Wheni=π, for j∈u, compute sπj=aj−cπyjmodq.(8)
OutputΩM=Ij,c1,sij,CR,M,R′i∈n,j∈u.A formal description of this algorithm is shown as Algorithm4.Algorithm 4: Sign (message, L, y).
Input:message∈0,1l, g,h,G∈G, R∈ℤq∗, L=PK1,…,PKnPKi=PKi1,…,PKiu, y.Output:ΩM=Ij,c1,sij,CR,M,R′i∈n,j∈u.(1)
LetH1message=μ.(2)
ComputeC=μg+Rh, CR=Rμg+RRh and e=H2C,CR where(3)
Rμ,RR⟶ℤq∗.(4)
ComputeM=eμ+Rμ, R′=eR+RR.(5)
for1≤j≤u do(6)
Chooseaπj←ℤq(7)
ComputeIj=yjHpPKπj; Lπj=aπjG;(8)
Rπj=aπjHpPKπj;(9)
end(10)
Computecπ+1=H3M,Lπ1,Rπ1,…,Lπu,Rπu.(11)
fori=π+1,…,n,1,…,π−1 do(12)
for1≤j≤u do(13)
Choosesij←ℤq(14)
ComputeLij=sijG+ciPKij;(15)
Rij=sijHpPKij+ciIj;(16)
end(17)
Computeci+1=H3M,Li1,Ri1,…,Liu,Riu;(18)
end(19)
for1≤j≤u do(20)
Computesπj=aj−cπyjmodq;(21)
end(22)
returnΩM=Ij,c1,sij,CR,M,R′i∈n,j∈u.Verify(1)
The verifier computese=H2C,CR. Then, checking whether eC+CR=Mg+R′h. If the congruence holds, return ″1″, otherwise ″0″.(2)
Fori∈n,j∈u, the verifier regenerates all the Lij,Rij,ci+1 and verifies whether cn+1=c1. If the congruence holds, return ″1″, otherwise ″0″.A formal description of this algorithm is shown Algorithm5.Algorithm 5: Verify(Ω, L).
Input:ΩM=Ij,c1,sij,CR,M,R′i∈n,j∈u,g,h∈G, L=PK1,…,PKnPKi=PKi1,…,PKiu.Output: 0 or 1.(1)
Computee=H2C,CR.(2)
ifeC+CR=Mg+R′h then(3)
for1≤i≤n do(4)
for1≤j≤u do(5)
ComputeLij=sijG+ciPKij;(6)
Rij=sijHpPKij+ciIj(7)
end(8)
Computeci+1=H3M,Li1,Ri1,…,Liu,Riu;(9)
end(10)
else(11)
0(12)
end(13)
ifcn+1=c1 then 1;(14)
else 0;(15)
return 0 or 1.Link.For a fixed set of public key-vectors, given two messagesM,M′, two valid signatures ΩM and Ω′M′, the verifier outputs link if the key image Ij=Ij′j∈u; otherwise the verifier outputs unlink.


## 5. Security Analysis

In this section, the security proofs of our scheme are given, which follow similarly to the security proofs of [4, 7].Theorem 1.
In ROM, the scheme is unforgeable if DL problem is hard.Proof.
(Similar proof to Theorem 6 of [4] and Theorem 1 of [7]) We follow the notation introduced above. Suppose that an adversary A can forge signature with nonnegligible probability; then we certainly can construct a PPT simulator C which can extract a solution to the DL problem. Given a random instance of the DL problem with security level κ, C is asked to solve the DL problem in polynomial time.
First of all,C maintains 4 lists ℓ1,ℓ2,ℓ3,ℓ4,ℓ5 in its local storage to store the outputs of H-oracle, H1-oracle, H3-oracle, key query, and sign query, initially setting to be empty. The interaction between A and C does as follows:
Initialization: Running theSetup algorithm; C gives A parameters.
Query: A is allowed to make the following queries (supposed that A will not initiate repeated queries).(1)
H query: C maintains list ℓ1 of tuple xi,TAGi. For a request of xi, if xi contains list ℓ1, C returns the corresponding tuple to A; otherwise, C randomly chooses TAGi∈0,1l and returns it to A; meanwhile, it stores the tuple xi,TAGi into list ℓ1.(2)
Hμ query: C maintains list ℓ2 of tuple message,M. For a request of message, if message contains list ℓ1, C returns the corresponding tuple to A; otherwise, C randomly chooses M and returns it to A; meanwhile, it stores the tuple message,M into list ℓ2.(3)
H3 query: C maintains list ℓ3 of tuple M,sij,ci,Li∈n,j∈u. For a request of M, a set L has n public key-vectors and randomly chooses sij∈ℤqi∈n,j∈u; if M,L contains list ℓ3,C returns the corresponding tuple to A; otherwise, C randomly chooses ci∈ℤq and returns it to A; meanwhile, it stores the tuple M,sij,ci,Li∈n,j∈u into list ℓ3.(4)
Key query: for a request ofxi, if the tuple xi,TAGi contains list ℓ1,C performs polynomial reconstruction function to generate f⋅ and the secret key si=f0 and returns it to A. Meanwhile, C stores the tuple xi,si into the ℓ4.(5)
Sign query: for a request ofmessage, the user’s biometric vector xi, and a set L of n public key-vectors where π is the real secret index, C generates a signature:(a)
Check listℓ4, if there exists xi, the real secret key sπ=yπ.(b)
Check listℓ2, if there exists message,M, the secret message is M.(c)
Forj∈u, compute Ij=yjHpPKπj.(d)
Forj∈u, choose aπj⟵ℤq and cπ+1⟵ℤq.(e)
Wheni=π+1,…,n,1,…,π−1:Forj∈u, choose sij⟵ℤq; compute Lij=sijG+ciPKij;Rij=sijHpPKij+cjIj;Computeci+1=H3M,Li1,Ri1,…,Liu,Riu, add sij,ci+1,CR,M,R′i∈n,j∈u into ℓ5. If collision occurs, repeat steps 3 and 5.(f)
OutputΩM=Ij,c1,sij,CR,M,R′i∈n,j∈u as a signature. It can be seen from the signing process that ΩM is a valid signature.
Forge:A outputs a forged signature ΩM∗=Ij∗,c1∗,sij∗,CR∗,M∗,R′∗i∈n,j∈u. Assume that A makes no more than q1+qH+uq3 queries to the signing oracles H1,H,H3 and SO.
From Lemma1, for each successful forgery A completes with transcript T, there are uT queries to H3 matching the n queries used to verify the signature. Let Xi1,…,Xiu denote the ith forgery and let π be the index for the last verification query; we have Xiℓ=H3M,Lπ−11,Rπ−11,…,Lπ−1uT,Rπ−1uT.
Ifi1=ℓ, A produces an attempted forgery Ω that is an ℓ,π-forgery. By assumption, there exists ℓ,π for giving a successful forgery; εℓ,πT satisfies(5)εℓ,π≥1uTq1+qH+uTq3⋅1Q1κ≥1uq1+qH+uq3⋅1Q1κ.
Then,A rewinds T before the ℓth query and again attempts a forgery on the same set of keys that T′ satisfies(6)εℓ,πT′≥1uq1+qH+uq3⋅1Q2κ,and also a successful forgery, where Q2 is a polynomial inputting a security parameter κ.
Therefore, the probability that bothT and T′ correspond to verifying forgeries Ω and Ω′ is nonnegligible:(7)εℓ,πT&T′≥εℓ,πT2.
In the way above, we again obtain a forged signatureΩM′=Ij′,c1′,sij′,CR′,M′,R″i∈n,j∈u. For each j, we have sπj≠sπj′,cπ≠cπ′, and we can solve yπj as(8)yπj=sπ′j−sπjcπ′−cπmodq,which contradicts the DL assumption.Theorem 2.
In ROM, the proposed scheme is signer-anonymous under the DDH assumption.Proof (similar proof to Theorem 8 of [4]).
Assume that the DDH problem is hard in the cyclic group generated byG and suppose there exists a PPT adversary A against signer ambiguity. After that, given a set L of n public key-vectors of length u, a set of t biometric vectors Dt=x1,…,xt, and a valid signature Ω on L signed by a user with respect to a key-vector PK¯ such that the corresponding biometric vector x¯π satisfies x¯π∉Dt, then, A can win the game above with probability(9)PrA⟶π≥1n−t+1Q3κfor some polynomial Q3κ. We certainly can construct a PPT simulator C which takes as inputs a tuple G,aG,bG,ciG, where i∈0,1 is randomly chosen and not a priori known to C, c1=ab, and c0 is a random scalar; then C can output i and solve the DDH problem with probability(10)PrCG,aG,bG,ciG⟶i≥12+1Q4κ,for some polynomial Q4κ.
Inputting scalarsa,c, the user’s biometric vector x, a set L of n public key-vectors of length u, index π, and message M, we act as follows.
Initialization, Query: it is the same as that in Theorem 1.
Challenge:A submits a new tuple M,xi,0,xi,1,L, where the public key-vectors corresponding to xi,0,xi,1 are in L. C flips a coin b∈0,1 and then returns A with the signature ΩM,xi,b,L.
Guess:A outputs a bit b′∈0,1.
Given a tupleG,aG,bG,ciG where a,b are randomly selected scalars, with c1=ab, c0 is a random scalar, i∈0,1, C takes the following steps to solve the DDH problem with nonnegligible probability.
Firstly,C grabs a private/public key-vector pair y¯,PK¯ from H1,H3 and a random γand computes s=a−γy. Then, C performs SIMNIZKP [4] with arbitrarily selected key-vectors PK¯ii∈n such that PK¯=PK¯π, a⟶a, ci⟶c, some message M, and y¯⟶y¯.
Ifi=1, then c=ab,logGaG=logbGcG=a; and due to the fact that A is assumed to be able to find π with nonnegligible probability, then there is a nonnegligible probability over 1/2 that A returns 1 (upon which C returns 1). Meanwhile, if i=0, then A returns 1 only with probability 1/2, and so for some nonnegligible probability over 1/2, C returns the same value as A and thus solves the DDH problem for randomly chosen scalars with nonnegligible probability over 1/2, which is a contradiction.Theorem 3.
In ROM, our scheme satisfies linkability.Proof (similar proof to Theorem 7 of [4]).
Suppose that aPPT adversary A can produce two unlinkable signatures Ω1,M1,L1 and Ω2,M2,L2 with nonnegligible probability, and they signed with respect to public key-matrices L1 and L2 such that there exists a public key PK in both L1 and L2 that is negligible.
Suppose to the contrary thatΩ1 and Ω2 both signed with respect to public key-matrices L1 and L2 such that there exists a public key PK in both L1 and L2, then with overwhelming probability, there exists the indexes π and π′ for the public keys in Ω1 and Ω2, respectively, such that(11)Lπj=sπjG+cπPKπj;Rπj=sπjHpPKπj+cπIj;Lπ′j′=sπ′j′G+cπ′PKπ′j′;Rπ′j′=sπ′j′HpPKπ′j′+cπ′Ij′.
Thus, we have(12)logGLπj=logHpPKπjRπj;logGLπ′j′=logHpPKπ′j′Rπ′j′.
ForIj and Ij′, it follows that Ij=yjHpPKπj=yjHpPK and Ij′=yjHpPK; the private key is related to the user’s biometric vector within U≥k. In this way, two signatures Ω1 and Ω2 include Ij=Ij′; since the duplicate key images are rejected, one of them must not verify.Theorem 4.
In ROM, our scheme is a NIZK argument of plaintext knowledge.Proof. In the above scheme, we have completeness, computational soundness, and zero-knowledge.
Proving procedures is as described in [12].


## 6. Efficiency Analysis

In this section, we give a brief efficiency comparison among the scheme of ours [4, 10]. The communication complexity of our scheme is almost Oun+1 where n is the number of public key vectors in each set. As shown in [4], the communication complexity of its scheme is also Oun+1. In contrast, it is On in [10].As shown in Table2, the cost of time and communication in our scheme is larger than [4, 10]. However, our scheme constructs a linkable ring signature scheme based on NIZK and SKE protocols to enhance the status of privacy-preserving, which is the vital improvement of our scheme.Table 2
Comparison of time and communication cost.
Ref.ProverVerifierCommunication[4]2.1un⋅exp1+un⋅Hq2.2un⋅exp1+un⋅HquG+H+unℤq[10]0.4n+1u+1⋅exp1+n+1⋅p+n+1⋅expT3.2λn+1⋅expq+1.1λ+0.4u+4n+1⋅exp+3n+1⋅p+2.2n+1⋅expTλ+5n+1G+3λ+6n+1ℤp+3λn+1ℤq+n+1GTOurs2.5un⋅exp1+un⋅Hq2.7un⋅exp1+un⋅Hqu+1G+H+un+2ℤq[∗] “n“: the number of public key-vectors in each set; “u“: the length of each public key-vector; “λ“: the length of element in ℤp; “exp1“: an exponentiation operation in group G1; “expT“: an exponentiation operation in group GT; “expq“: an exponentiation operation in group Gq⊂ℤp∗; “p“: a bilinear pairing operation; Hp: a map-to-point hash function; H: the output size of a hash function H; G1: the length of element in group G1, similarly for ℤp,ℤq, and GT.


## 7. Experiments and Discussion

In this section, we present a simple demonstration of our scheme by usingPython.


### 7.1. Parameters

In order to get fingerprint vectors, we adopt the idea of fingerprint image conversion to fingerprint vector which is consisted of several sequential stages: getting fingerprint image, preprocessing, and taking attribute values for feature key points. For each user, one of the fingerprint vectors is used forSetup, and other fingerprint vectors from the same user are used to retrieve the secret key with the procedure described in Section 5.In order to preserve the accuracy performance at the same level as in the original fingerprint in [5], we choose the appropriate parameters of SKE algorithm to control FAR, FRR, and EER within a suitable range in our experiments. Meanwhile, these parameters can also get a theoretically favorable level of the computational security to resist the brute-force and false-accept attacks. For all the experiments, we choose m=1024, q=251, q′=280 for the dataset (FVC 2002 subset DB1, DB2) with k=18.As for the signing process, we make improvements based on the original Ring CT [4] codes by adding the SKE and NIZK protocols. In this way, we generate a new code for our scheme. Specifically, we use Keccak-256 hash function to generate the secret keys as well as the public keys and set parameters of the elliptic curve as same as Ed25519. We implemented our scheme in Intel Core i52.5 GHz, 4 Gb RAM, MacOS 10.13.6. Each element in ℤq is represented by 32 bytes.


### 7.2. Experimental Results

For a small ring size, we repeat the signing and verification process separately withn=6,8,10,12 and u=4,6,8,10. The experimental results are presented in Table 1.For a relatively large ring size, we repeat the signing and verification process; the experimental results are presented in Figure3.Figure 3
Performance of our shame. (a) Running time of sign. (b) Running time of verify.
(a)(b)As shown in Figure3, the running time of signature in our scheme increases linearly with the number of group accounts. Meanwhile, the running times of signing and verification process are almost the same. It also can be concluded from the construction of our scheme.As shown in Table3, when we use a small ring size in our signature scheme, the simulation experiment can be carried out by using an ordinary personal computer. The result of experiment may have some abnormal deviations for different computer hardware, but overall it represents the results of our scheme where we run the scheme on our personal computer. This is useful for mobile demonstration in section 7. According to the experimental results above, we can see that our scheme can meet the needs of practical applications.Table 3
Average running time of every step for different ring numbers and public keys.
Average running timen=6n=8n=10n=12SignVerifySignVerifySignVerifySignVerifyu=42.742.323.163.044.083.764.894.72u=62.972.774.454.216.536.508.067.81u=84.334.186.976.349.138.8411.5311.10u=106.195.948.868.2212.1711.9015.3214.95


## 7.1. Parameters

In order to get fingerprint vectors, we adopt the idea of fingerprint image conversion to fingerprint vector which is consisted of several sequential stages: getting fingerprint image, preprocessing, and taking attribute values for feature key points. For each user, one of the fingerprint vectors is used forSetup, and other fingerprint vectors from the same user are used to retrieve the secret key with the procedure described in Section 5.In order to preserve the accuracy performance at the same level as in the original fingerprint in [5], we choose the appropriate parameters of SKE algorithm to control FAR, FRR, and EER within a suitable range in our experiments. Meanwhile, these parameters can also get a theoretically favorable level of the computational security to resist the brute-force and false-accept attacks. For all the experiments, we choose m=1024, q=251, q′=280 for the dataset (FVC 2002 subset DB1, DB2) with k=18.As for the signing process, we make improvements based on the original Ring CT [4] codes by adding the SKE and NIZK protocols. In this way, we generate a new code for our scheme. Specifically, we use Keccak-256 hash function to generate the secret keys as well as the public keys and set parameters of the elliptic curve as same as Ed25519. We implemented our scheme in Intel Core i52.5 GHz, 4 Gb RAM, MacOS 10.13.6. Each element in ℤq is represented by 32 bytes.


## 7.2. Experimental Results

For a small ring size, we repeat the signing and verification process separately withn=6,8,10,12 and u=4,6,8,10. The experimental results are presented in Table 1.For a relatively large ring size, we repeat the signing and verification process; the experimental results are presented in Figure3.Figure 3
Performance of our shame. (a) Running time of sign. (b) Running time of verify.
(a)(b)As shown in Figure3, the running time of signature in our scheme increases linearly with the number of group accounts. Meanwhile, the running times of signing and verification process are almost the same. It also can be concluded from the construction of our scheme.As shown in Table3, when we use a small ring size in our signature scheme, the simulation experiment can be carried out by using an ordinary personal computer. The result of experiment may have some abnormal deviations for different computer hardware, but overall it represents the results of our scheme where we run the scheme on our personal computer. This is useful for mobile demonstration in section 7. According to the experimental results above, we can see that our scheme can meet the needs of practical applications.Table 3
Average running time of every step for different ring numbers and public keys.
Average running timen=6n=8n=10n=12SignVerifySignVerifySignVerifySignVerifyu=42.742.323.163.044.083.764.894.72u=62.972.774.454.216.536.508.067.81u=84.334.186.976.349.138.8411.5311.10u=106.195.948.868.2212.1711.9015.3214.95


## 8. Anonymous Cryptocurrency Transaction Model Based on LRS Scheme

Based on the proposed scheme and demonstration above, we propose a relatively private cryptocurrency model. Based on the experimental results on PC and private cryptocurrency model, we design a mobile simulation interface which means it may have a practical application value in mobile phone.In the transaction schematics (Figure4), we suppose that Alice sends money to Bob. In this process, Alice’s anonymity is protected by ring signature and NIZK protocol. One-time address is used to protect Bob’s anonymity. Moreover, we use SKE algorithm to protect secret key on both sides and use linkable tag to prevent double spending.(1)
During the registration phase (Figure5(a)), while Alice enters the personal information and password as prompted, she also takes the fingerprint photo at the same time. On the input information above, the system runs the biometric encryption algorithm SKE to encrypt Alice's password. In other words, the system runs Setup (x) algorithm and stores the public helper data PP.(2)
In the login page (Figure5(b)), Alice uses the new fingerprint to unlock the interface. On input of the new fingerprint x′ (the query biometric vector in the Section 2 part A), the system runs KeyGen (x′) algorithm to recover the password through the public helper data PP in step 1. Similarly, Bob does the same operations.(3)
As shown in Figure5(c), Alice transfers the money to Bob. In addition, for multilayer ring signature scheme, Alice chooses the number n. Note could be indicated in remarks column, if it has. Finally, Alice clicks on the sign button to sign for this transaction. For system, Alice generates a one-time address for Bob, and no one other than Bob (including Alice) can recover the full signature key. Then, the system selects the n−1 addresses to get the equivalent amount of currency. Thus, the system inputs all Alice’s previous transactions into a hash function and obtains the hash value. Using the NIZK algorithm stated above to blind the message M in Figure 4(c), the system runs signature algorithm to obtain ΩM. Finally, the system generates a transaction Tx and broadcasts Tx throughout the P2P network (Figure 5(d)).(4)
In the verification phase (Figure5(e)), everyone in the P2P network can verify our transactions without knowing our plain message.Figure 4
Cryptocurrency transactions model.Figure 5
Mobile demonstration interface.
(a)(b)(c)(d)(e)However, we do not use an authentication mechanism in the registration phase which will reduce the security of cryptocurrency transactions model. To deal with this issue, we consider using the following two-factor or three-factor authentication mechanisms. Stanislaw et al. [23] presented a secure two-factor authentication system based on the possession by the user of a password and a cryptocapable device which can achieve end-to-end security. Qiu et al. [24] put forward a provably secure three-factor protocol for mobile lightweight devices, which can achieve truly three-factor security while providing password change friendliness. Wang et al. [25] advanced a new two-factor authentication mechanism to resolve the various issues arising from user corruption and server compromise. Jiang et al. [26] proposed a cloud-centric three-factor authentication and key agreement protocol integrating passwords, biometrics, and smart cards to ensure secure access to both cloud and autonomous vehicles.


## 9. Conclusion

In this paper, we construct a linkable ring signature scheme based on NIZK and SKE protocols to enhance the status of privacy-preserving. In our signature scheme, we use the SKE algorithm to protect the secret key. Simultaneously, we also use the NIZK protocol to encrypt the plain message without revealing redundant information of the message in the verification process. With respect to the NIZK part, the NIZK protocol we used satisfies three characteristics: completeness, soundness, and zero-knowledge. At the same time, our scheme holds unforgeability, anonymity, and linkability in ROM. We also demonstrate the practical performance of our scheme on a personal computer. The result provides us with strong confidence in applying our scheme in practice.However, since we apply the SKE and NIZK protocols to original Ring CT scheme to encrypt the secret key and the message, the running time and communication cost of our scheme have slightly increased. Although our signature scheme may meet a real need, we will improve our scheme to reduce the running time and communication cost in our future work. In addition, the security of our scheme is based on the hardness of the DL problem, which is vulnerable to quantum attacks. In the future research, we will improve our scheme based on postquantum cryptography.



---

*Source: 7266564-2021-12-15.xml*