# A Novel Biometric Identification Scheme Based on Zero-Knowledge Succinct Noninteractive Argument of Knowledge

Authors: Chunjie Guo; Lin You; Gengran Hu
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Biometric identification is a convenient and reliable method in identity authentication. The widespread adoption of biometric identification requires strong privacy protection against possible theft or loss of biometric data. Existing techniques for privacy-preserving biometric identification mainly rely on traditional cryptographic technology such as oblivious transfer and homomorphic encryption, which will incur huge expenses to the system and cannot be applied to large-scale practical applications. For these issues, we propose a biometric identification scheme by constructing zero-knowledge succinct noninteractive argument of knowledge (zk-SNARK). Our scheme not only reduces the communication overhead, which only needs to send 8 constants to the verifier but also can protect the fingerprint template from disclosure. The time complexity of proof generation and proof verification are aboutO(C) and Ox+logC, respectively, and the size of the proof is only 8 constants, where C and x represent the size of the circuit and the public input, respectively. We have implemented the proposed authentication solution on a public data set of fingerprint images and evaluated the performance and security.


---

## Body

## 1. Introduction

In the field of e-government, the security of data requires that the data cannot leave the third-party security center; at the same time, there are requirements for data circulation, which requires outsourcing companies to achieve some business functions but cannot disclose secret information to outsourcing companies. The combination of biometrics and zero-knowledge proof can solve the private problems of templates in traditional biometric identification. There is no need to disclose template information to outsourcing companies, and the security center only need to prove to the outsourcing company that the verification is successful, which can maximize the benefit of society in the areas of credit assessment, risk prevention and control, monitoring and medical care, and so on.Liu Yuqin et al. [1] classified identity authentication into three categories mainly, which are based on specific knowledge, based on markers, and based on biometrics [2]. Identity authentication based on biometrics is the most secure method currently, which is to store the extracted biometrics of the user in the database as a template. This method can avoid database collision attacks and is also user-friendly [3]. A lot of works on biometric authentication have been done, but most of the works are focused on improving the recognition accuracy of biometric authentication. Some biometric recognition methods based on neural networks have reached nearly 100% recognition accuracy. Although many identification methods can meet people’s requirements for authentication accuracy, how to achieve more secure identity authentication is particularly important and practical. The security of biometric template is particularly important in the biometric identification scheme based on privacy protection. Jain et al. [4] divided the existing schemes for protecting biometric template into two types, namely, feature transformation and biometric encryption. However, these two methods often restricted each other between security and accuracy and cannot achieve high-security identity authentication in a complex network environment. The proposal and development of zero-knowledge proof (ZKP) technology provides new ideas for secure biometric authentication. Yu et al. [5] achieved zero knowledge against the verifier. Li et al. [6] presented the primitive of fuzzy identity-based data auditing. Li et al. [7] proposed two possible solutions to balance privacy and regulation of blockchain-based cryptocurrencies. Li et al. [8] proposed a new cryptocurrency named Traceable Monero to balance the user accountability and anonymity.ZKPs introduced by Goldwasser et al. [9] are the underlying technology of blockchain. ZKPs enable a prover to convince a verifier of the authenticity of a statement without leaking any other information. ZKPs have three important properties of completeness, soundness, and zero-knowledge. The important function of zero-knowledge proof is to protect data privacy. In 1988, Feige et al. [10] proved that zero-knowledge proof can enable the litigant to prove his identity by proving that he has certain knowledge rather than by proving the validity of the assertion. In other words, zero-knowledge proofs can be applied in the digital identity system with the function of identity information privacy protection.Bitansky et al. [11] gave the definition of zk-SNARK for the first time and proved its existence. zk-SNARK proposed by Ben-Sasson et al. in 2014 is used in Zcash. Since then, various zk-SNARKs have appeared in recent years, for example, Groth 16 [12] (adopted by Zcash), GKM +1 8, Bulletproof [13], Sonic [14], Marlin19 [15], Plonk [16], Halo [17], Fractal [18], SuperSonic [19] etc. [27–29], of which only Groth 16 requires trusted settings. Bulletproof is an efficient zero-knowledgeness proof suitable for range proof, and it has been applied in the Monero coin blockchain system. Plonk was an optimized and improved version of Sonic, and the verification time is greatly reduced. At the 2020 European Secret Conference, Benedikt et al. [19] also proposed an optimized version of Sonic, SuperSonic, whose proof size and verification time are only logarithmic. Based on zk-SNARK (Groth 16), Guan et al. [12] proposed a blockchain Block Maze, an account model that can effectively hide account balances, transaction amounts, and privacy protection functions associated with the sender and receiver.


### 1.1. Contributions

A biometric identification scheme based on the zk-SNARK is proposed to address the problem of avoiding leakage of biometric templates information. In this work, we focus on using zk-SNARK to hide sensitive biological information as private input to achieve the effect of zero-knowledgeness.We extract fingerprints feature points as biometric features because of their inherent uniqueness, persistence, accuracy, and ease of use. In order to improve the efficiency of the scheme, we group the collected fingerprint feature points.In the scheme, the Euclidean distance of the two fingerprints feature points (biometric templates and extracted biological features) is expressed in binary form; then, we transform the problem into a polynomial domain to improve efficiency.We implemented the proposed biometric identification on a public data set of fingerprint images and evaluated the performance and security. We also calculated the proof time, verify time, R1CS time, QAP time, and certificate time consumption of each stage corresponding to the number of different fingerprint features.


### 1.2. Structure of the Paper

In Section2, some mathematical symbols, bilinear group, arithmetic circuits, and quadratic arithmetic programs, the knowledge of coefficient test and assumption for quadratic arithmetic programs and noninteractive zk-SNARK are described. The construction of our scheme is described in Section 3. Security description and performances analysis are in Section 4. The conclusion is described in Section 5.


## 1.1. Contributions

A biometric identification scheme based on the zk-SNARK is proposed to address the problem of avoiding leakage of biometric templates information. In this work, we focus on using zk-SNARK to hide sensitive biological information as private input to achieve the effect of zero-knowledgeness.We extract fingerprints feature points as biometric features because of their inherent uniqueness, persistence, accuracy, and ease of use. In order to improve the efficiency of the scheme, we group the collected fingerprint feature points.In the scheme, the Euclidean distance of the two fingerprints feature points (biometric templates and extracted biological features) is expressed in binary form; then, we transform the problem into a polynomial domain to improve efficiency.We implemented the proposed biometric identification on a public data set of fingerprint images and evaluated the performance and security. We also calculated the proof time, verify time, R1CS time, QAP time, and certificate time consumption of each stage corresponding to the number of different fingerprint features.


## 1.2. Structure of the Paper

In Section2, some mathematical symbols, bilinear group, arithmetic circuits, and quadratic arithmetic programs, the knowledge of coefficient test and assumption for quadratic arithmetic programs and noninteractive zk-SNARK are described. The construction of our scheme is described in Section 3. Security description and performances analysis are in Section 4. The conclusion is described in Section 5.


## 2. Preliminaries

### 2.1. Notation

Table1 shows the symbols and descriptions used in this article. We write y←Ax;r when algorithm A on input x and randomness r, outputs y. y⟶S means to sample y randomly and evenly from the set S.Table 1
The symbols and the descriptions.
NotationDescriptionsG1,G2 and GTGroups of prime orderpg1A generator forG1g2A generator forG2e(g1, g2)The pairinge is a bilinear mapx1g1xx2g2xxTeg1,g2xN1,2,…,nfλ≈0f is negligiblefλ≈1f is overwhelmingSvThe supervisor/verifierPThe user/prover (honest)Bioi,jFingerprint feature point templateBioi,j′Fingerprint feature point extracted for the second timeKn1,k,k2,…,kn−1∈Fp∗nδThe public threshold of Euclidean distancePA prime numberFpA finite field of order pE1,E2Two homomorphic mappings represent the coordinates of thejth fingerprint feature of thea1,j′,b1,j′First set collected for the second time


### 2.2. Bilinear Groups

We will study over bilinear groupsp,G1,G2,e,g1,g2 with the following properties:(i)
Bilinearity:eg1a,g2b=eg1,g2ab for all g1∈G1, g2∈G2, a,b∈Zp(ii)
Nondegeneracy: there existsg1∈G1 , g2∈G2 such that eg1a,g2b≠1GT(iii)
Computability:eg1,g2 can be calculated by an efficient algorithm for all g1∈G1, g2∈G2Galbraith et al. [20] classified bilinear groups as type I, where G1 = G2, type II, where there is an efficiently computable nontrivial homomorphism Ψ:G2⟶G1, and type III, where does not exist to efficiently computable homomorphism in either direction between G1 and G2. Type III is the most efficient type of bilinear groups, so it is suitable to be used in practical applications. Our scheme can be implemented on the above three types of bilinear groups.


### 2.3. The Knowledge of Coefficient Test and Assumption (KCA) for Quadratic Arithmetic Programs

Forα∈Fp, let us call a pair of elements (a, b) in G an α-pair if a,b≠0 and b=αa.The KCA proceeds as follows:(1)
Verifier chooses randomα∈Fp∗ and α∈G computes b=αa and then sends “challenge” pair (a, b) to the prover. Note that (a, b) is an α-pair.(2)
Prover must now respond with a different paira′,b′ that is also an α-pair.Verifier accepts prover’s response only ifa′,b′ is indeed an α-pair (as he knows α he can check if b′ = αa′).In general, if we know a set ofα-pair: p1,q1,p2,q2,…,pn,qn, then the only way to generate a new α-pair is to compute a linear combination of them. In other words, if you output a new (P, Q) you have to know the combination coefficient among them s1,s2,…,sn, s1,s2,…,sn satisfies P=s1p1+s2p2+⋯snpn, Q=s1q1+s2q2+⋯snqn.


### 2.4. Noninteractive Zero-Knowledge Arguments of Knowledge

A relation generatorR that given an unary security parameter λ returns a binary relation R that can be determined by polynomial time. For pairs ϕ,ω∈R, we say ϕ is the statement and ω is the witness. For simplicity, we will in the following assume λ can be deduced from the description of R. An efficient publicly verifiable noninteractive argument containing four probabilistic polynomial algorithms (Setup, Prove, Verify, Sim) are as follows:σ,τ←SetupR: it returns a common reference string (CRS) σ and a simulation trapdoor τ when you input relation R.π←ProveR,σ,ϕ,ω: it returns an argument π when you input a CRS σ and ϕ,ω∈R.yes/no←VerifyR,σ,ϕ,π: it returns no or yes when you input a CRS σ , a statement ϕ and an argument π.π←SimR,τ,ϕ: it returns an argument π when you input a simulation trapdoor τ and statement ϕ.Perfect completeness: if an honest prover knows any true statement, he can convince an honest verifier. For allλ∈ℕ, R∈Rλ, ϕ,ω∈R(1)Prσ,τ←SetupR;π←ProveR,σ,ϕ,ω:VerifyR,σ,ϕ,π=1=1.Computational soundness: we say it is sound if it is not possible to prove a false statement. We require that the adversariesA.(2)PrR,z←R1λ;σ,τ←SetupR;ϕ,π←AR,z,σ:ϕ∉LR,VerifyR,σ,ϕ,π=1≈0.Perfect zero-knowledge: we say it is perfect zero-knowledge if for allλ∈ℕ , R,z←R1λ, ϕ,ω∈R and all adversaries A.(3)Prσ,τ←SetupR;π←ProveR,σ,ϕ,ω:AR,z,σ,τ,π=1=Prσ,τ←SetupR;π←SimR,τ,ϕ:AR,z,σ,τ,π=1.Definition 1.
We say (Setup, Prove, Verify, Sim) is a perfect noninteractive zero-knowledge argument of knowledge forR if it has perfect completeness, perfect zero-knowledge, and computational knowledge soundness.


### 2.5. Arithmetic Circuits and Quadratic Arithmetic Programs (QAP)

Like Boolean circuits, arithmetic circuits can be represented by graphs with edges and vertices as wires and gates, respectively [21]. Each input and output of a gate can be assigned a value. Whether the allocation is effective or not is related to the circuit. The idea behind the zk-SNARK protocol using arithmetic circuits is to convert valid circuit assignments into algebraic properties of polynomials, using QAP.Definition 2 (see [22]).
A QAPQ over field F contains three sets of polynomials A=aix:i∈1,2,⋯,n, B=bix:i∈1,2,⋯,n, C=cix:i∈1,2,⋯,n, and a target polynomial t(x), all from F[X].
Letf be a function with input variables labeled 1,2,…,n and output variables labeled m−n′+1,…,m. Q is a QAP that computes f if the following is true: s1,s2,…,sn,sm−n′+1,…,sm∈Fn+n′ is a valid assignment to the input/output variables of f if there exists sn+1,…,sm−n′∈Fm−n−n′ such that t(x) divides a0x+∑i=1msi⋅aix⋅b0x+∑i=1msi⋅bix-c0x+∑i=1msi⋅cix. The size of Q is m, deg (t(x)) represents the degree of Q.
We let the degrees of all.aix⋅si, bix⋅si, and cix⋅si is at most deg (t(x) − 1) because they can all be reduced by modulo t(x) without affecting the divisibility check (the check whether t(x) divides the expression).


## 2.1. Notation

Table1 shows the symbols and descriptions used in this article. We write y←Ax;r when algorithm A on input x and randomness r, outputs y. y⟶S means to sample y randomly and evenly from the set S.Table 1
The symbols and the descriptions.
NotationDescriptionsG1,G2 and GTGroups of prime orderpg1A generator forG1g2A generator forG2e(g1, g2)The pairinge is a bilinear mapx1g1xx2g2xxTeg1,g2xN1,2,…,nfλ≈0f is negligiblefλ≈1f is overwhelmingSvThe supervisor/verifierPThe user/prover (honest)Bioi,jFingerprint feature point templateBioi,j′Fingerprint feature point extracted for the second timeKn1,k,k2,…,kn−1∈Fp∗nδThe public threshold of Euclidean distancePA prime numberFpA finite field of order pE1,E2Two homomorphic mappings represent the coordinates of thejth fingerprint feature of thea1,j′,b1,j′First set collected for the second time


## 2.2. Bilinear Groups

We will study over bilinear groupsp,G1,G2,e,g1,g2 with the following properties:(i)
Bilinearity:eg1a,g2b=eg1,g2ab for all g1∈G1, g2∈G2, a,b∈Zp(ii)
Nondegeneracy: there existsg1∈G1 , g2∈G2 such that eg1a,g2b≠1GT(iii)
Computability:eg1,g2 can be calculated by an efficient algorithm for all g1∈G1, g2∈G2Galbraith et al. [20] classified bilinear groups as type I, where G1 = G2, type II, where there is an efficiently computable nontrivial homomorphism Ψ:G2⟶G1, and type III, where does not exist to efficiently computable homomorphism in either direction between G1 and G2. Type III is the most efficient type of bilinear groups, so it is suitable to be used in practical applications. Our scheme can be implemented on the above three types of bilinear groups.


## 2.3. The Knowledge of Coefficient Test and Assumption (KCA) for Quadratic Arithmetic Programs

Forα∈Fp, let us call a pair of elements (a, b) in G an α-pair if a,b≠0 and b=αa.The KCA proceeds as follows:(1)
Verifier chooses randomα∈Fp∗ and α∈G computes b=αa and then sends “challenge” pair (a, b) to the prover. Note that (a, b) is an α-pair.(2)
Prover must now respond with a different paira′,b′ that is also an α-pair.Verifier accepts prover’s response only ifa′,b′ is indeed an α-pair (as he knows α he can check if b′ = αa′).In general, if we know a set ofα-pair: p1,q1,p2,q2,…,pn,qn, then the only way to generate a new α-pair is to compute a linear combination of them. In other words, if you output a new (P, Q) you have to know the combination coefficient among them s1,s2,…,sn, s1,s2,…,sn satisfies P=s1p1+s2p2+⋯snpn, Q=s1q1+s2q2+⋯snqn.


## 2.4. Noninteractive Zero-Knowledge Arguments of Knowledge

A relation generatorR that given an unary security parameter λ returns a binary relation R that can be determined by polynomial time. For pairs ϕ,ω∈R, we say ϕ is the statement and ω is the witness. For simplicity, we will in the following assume λ can be deduced from the description of R. An efficient publicly verifiable noninteractive argument containing four probabilistic polynomial algorithms (Setup, Prove, Verify, Sim) are as follows:σ,τ←SetupR: it returns a common reference string (CRS) σ and a simulation trapdoor τ when you input relation R.π←ProveR,σ,ϕ,ω: it returns an argument π when you input a CRS σ and ϕ,ω∈R.yes/no←VerifyR,σ,ϕ,π: it returns no or yes when you input a CRS σ , a statement ϕ and an argument π.π←SimR,τ,ϕ: it returns an argument π when you input a simulation trapdoor τ and statement ϕ.Perfect completeness: if an honest prover knows any true statement, he can convince an honest verifier. For allλ∈ℕ, R∈Rλ, ϕ,ω∈R(1)Prσ,τ←SetupR;π←ProveR,σ,ϕ,ω:VerifyR,σ,ϕ,π=1=1.Computational soundness: we say it is sound if it is not possible to prove a false statement. We require that the adversariesA.(2)PrR,z←R1λ;σ,τ←SetupR;ϕ,π←AR,z,σ:ϕ∉LR,VerifyR,σ,ϕ,π=1≈0.Perfect zero-knowledge: we say it is perfect zero-knowledge if for allλ∈ℕ , R,z←R1λ, ϕ,ω∈R and all adversaries A.(3)Prσ,τ←SetupR;π←ProveR,σ,ϕ,ω:AR,z,σ,τ,π=1=Prσ,τ←SetupR;π←SimR,τ,ϕ:AR,z,σ,τ,π=1.Definition 1.
We say (Setup, Prove, Verify, Sim) is a perfect noninteractive zero-knowledge argument of knowledge forR if it has perfect completeness, perfect zero-knowledge, and computational knowledge soundness.


## 2.5. Arithmetic Circuits and Quadratic Arithmetic Programs (QAP)

Like Boolean circuits, arithmetic circuits can be represented by graphs with edges and vertices as wires and gates, respectively [21]. Each input and output of a gate can be assigned a value. Whether the allocation is effective or not is related to the circuit. The idea behind the zk-SNARK protocol using arithmetic circuits is to convert valid circuit assignments into algebraic properties of polynomials, using QAP.Definition 2 (see [22]).
A QAPQ over field F contains three sets of polynomials A=aix:i∈1,2,⋯,n, B=bix:i∈1,2,⋯,n, C=cix:i∈1,2,⋯,n, and a target polynomial t(x), all from F[X].
Letf be a function with input variables labeled 1,2,…,n and output variables labeled m−n′+1,…,m. Q is a QAP that computes f if the following is true: s1,s2,…,sn,sm−n′+1,…,sm∈Fn+n′ is a valid assignment to the input/output variables of f if there exists sn+1,…,sm−n′∈Fm−n−n′ such that t(x) divides a0x+∑i=1msi⋅aix⋅b0x+∑i=1msi⋅bix-c0x+∑i=1msi⋅cix. The size of Q is m, deg (t(x)) represents the degree of Q.
We let the degrees of all.aix⋅si, bix⋅si, and cix⋅si is at most deg (t(x) − 1) because they can all be reduced by modulo t(x) without affecting the divisibility check (the check whether t(x) divides the expression).


## 3. Our Proposed Scheme

In the section, first of all, we outline the main idea of the biometric identification scheme based on zk-SNARK and then the design of its three stages is introduced. The symbols are described in Table1.


### 3.1. Scheme Overview

In our construction, we divided our scheme into three stages: extract fingerprint feature points, construction of biometric identification based on zk-SNARK, and verification. Extract fingerprint feature points: first of all, we need to segment the fingerprint region from the background of the image, then we select the minutiae as the fingerprint feature points, and finally, the fingerprint feature points are represented in the plane right-angle coordinates and the feature points are sorted according to the distance from the center point. Construction of biometric identification based on zk-SNARK: the proverP constructs a ZKP on the basis of the known template and the second collected fingerprint feature points, which makes the verifier Sv believe whether the second collected fingerprint feature and the template are from the same person’s fingerprint without leaking the template. Verification: according to the proof provided by the prover and some public information CRS, the verifier verifies whether the prover is correct or not. The framework of biometric identification is described in Figure 1.Figure 1
Framework of biometric identification.


### 3.2. Extract Fingerprint Feature Points

The preprocessing of the fingerprint image goes through eight steps as shown Figure2:(1)
Fingerprint preprocessing: in the process of fingerprint preprocessing, the method in [23] is adopted. First of all, the fingerprint image is divided into 3∗3 blocks, and then the mean value and variance value are calculated in each block for segmenting the fingerprint area. Finally, enhance the fingerprint image to produce a fingerprint skeleton image. Here, the cross number method is used to extract the end points and the bifurcation points of the fingerprint features.(2)
Selection and representation of feature points: It is necessary to select the extracted feature points to avoid the situation that the extracted minutiae have many pseudominutiae (such as the edge part and the blurred part of the fingerprint image) due to the influence of external factors such as noise. For matching the input of the fuzzy extractor, the selected feature points need to be represented in an appropriate form.(i)
Selection of the center point: now, the Poincare [24] indexing algorithm is the most commonly used method to find the center point which may not be accurate enough (for example, the center area of a fingerprint is obtained instead of a specific point), but do not affect our approach, because we do not directly use it as a reference point for feature extraction or fingerprint comparison, but take the region where the central point is located as a reference and select several minutiae around the central point.(ii)
Selection of the minutiae point: we use the cross number method to detect fingerprint endpoints or bifurcations. If the selected minutiae points are too many, it will increase the verification time, if too few, the uniqueness of the fingerprint will not be obvious. So, we should select appropriate number of minutiae points to represent the characteristics of the whole fingerprint. First of all, we let the minimum sampling radiusRmin=40px (px represents picture pixels). Then, the end point of the fingerprint ridge line is selected as the reference point; after that, we establish a polar coordinate system. (0, 0) is the center point of the coordinates, and the coordinates of any minutiae point mk is ρk,θk. For any minutiae point, if it satisfies ρ>Rmin, it will be a candidate minutiae point. Meanwhile, we select the nearest 3n minutiae points closest to center point and add them to the selection queue.(iii)
Sorting of the minutiae point. The minutiae selected in the previous step are sorted from small to large inθ value. Then, a set of minutiae points mk, k∈3n is formed, in which 3n is the number of effective minutiae points selected. Mk=ρ,θk, ρ is the distance from the center point, and θk is the angle relative to the polar axis.(3)
Feature point processing: convert polar coordinatesmk, k∈3n to rectangular coordinates Mk, k∈3n as fingerprint feature points. The method is as follows: Biok=xk,yk, where xk=ρcosθk and yk=ρsinθk. We divide the 3n fingerprint feature points into n groups; 3 fingerprint feature points in each group, that is, Bioi,ji∈n, j∈1,2,3. We save Bioi,ji∈n, j∈1,2,3 as a template to the third-party security center (Figure 3). Take the same method for the second time to get Bioi,j′, i∈n, j∈1,2,3, and do not need to save Bioi,j′, i∈n, j∈1,2,3,(4)
Matching: calculate Euclidean distanceη=DisBioi,j′,Bioi,j,i∈n,j∈1,2,3, respectively. Compare the size of ηi and the threshold δ, respectively, if half of the ηi are less than or equal to δ, the authentication is passed, or the authentication is not passed. The framework of the matching is described in Figure 4.Figure 2
Eight stages of fingerprint preprocessing (original image, binarization, background separation, texture mask, texture enhancement, texture characterization, feature point calculation, and center feature extraction).Figure 3
Framework of extracting fingerprint templates.Figure 4
The outline of the matching.


### 3.3. Construction of Biometric Identification Based on Zero-Knowledge Proof

For security reasons,P can obtain the template Bioi,j, i∈n, j∈1,2,3, by obtaining the authorization of third-party security center through the private key. Bioi,ji∈n, j∈1,2,3 is kept secret Sv. That is, P can get the template Bioi,j and the fingerprint information Bioi,j′ collected for the second time. Sv only gets the fingerprint information Bioi,j′ collected for the second time. Since Bioi,j, i∈n, j∈1,2,3, is kept secret Sv, ηi=DisBioi,j′,Bioi,j,i∈n,j∈1,2,3, cannot be calculated directly, and a ZKP needs to be used.The goal of our scheme is using the idea of zk-SNARK to convince theSv that Bioi,ji∈n, j∈1,2,3 and Bioi,j′, i∈n, j∈1,2,3 satisfy the distance threshold condition ηi, i∈n is less than or equal to δ, that is, ηi∈0,δ, i∈n. P uses the following three-step strategy to prove to Sv that Bioi and Bioi′ satisfy the distance threshold condition ηi∈0,δ, i∈n. The scheme performs a total of n zk-SNARKs. Take the first group as an example to elaborate on the whole process. We suppose Bio1,j′=a1,j′,b1,j′,a2,j′,b2,j′,a3,j′,b3,j′ and Bio1,j=a1,j,b1,j,a2,j,b2,j,a3,j,b3,j, j∈1,2,3:(1)
Convert the arithmetic equations into a circuitCThe arithmetic equations:(4)∑j=13b1,j−b1,j′2+a1,j−a1,j′2=20ω0+21ω1+⋯+2tωt,ω∈0,1δ2=2t+1−1.The arithmetic equations are covered into the circuitC (Figure 5).The constraints of circuitC (it is transformed into t + 7 constraints):(5)ωiωi−1=0,i∈1,2,…,t,δ2=2t+1−1,y1,j=a1,j−a1,j′2+b1,j−b1,j′2,j∈1,2,3,η1=∑j=13y1,j,η1=20ω0+21ω1+⋯+2tωt.(2)
Convert constraints to R1CS.Lets=1,ω0,ω1,⋯,ωt,a1,j,a1,j′,b1,j,b1,j′,y1,j,η1 find the three matrices a, b, and c for each constraint s⋅a×s⋅b=s⋅c, that is t + 7 constraints, so a, b, and c are three (t + 7) × (t + 18) matrices.(3)
Convert R1CS to QAP.According to Lagrange interpolation, three polynomial matrices of degreet + 6 can be obtained.(6)AX=A1X,A2X,…,At+18X,BX=B1X,B2X,…,Bt+18X,CX=C1X,C2X,…,Ct+18X.s meets PX=s⋅AX×s⋅BX−s⋅CX=HXZX, where ZX=X−1X−2⋯X−t+7, H(X) = P(X)/Z(X).The equation holds whenX=1,2,⋯,t+7 to satisfy all constraints.We will now construct a noninteraction zero knowledge for QAP generators that outputs relations of the form:(7)R=s|s=1,ω0,ω1,…,ωt,a1,b1,j,b1,j′,y1,j,η1s⋅AX×s⋅BX=s⋅CX.The relation defines a language of witnesses and statements (public and private inputs).s=1,ω0,ω1,…,ωt,a1,j,a1,j′,b1,j,b1,j′,y1,j,η1,j∈1,2,3 such that:(8)s⋅AX×s⋅BX−s⋅CX=HXZX.(1)
SetupR←CRS: introduce third-party trusted settings to generate random numbers αA, αB, αC,β,z, which keep secret from P and Sv, and can then be discarded. For the convenience of writing, we set si=1t+18=1,ω0,ω1,…,ωt,a1,j,a1,j′,b1,j,b1,j′,y1,j,η1,j∈1,2,3. We define AX=∑i=1t+18si×AiX,BX=∑i=1t+18si×BiX,CX=∑i=1t+18si×CiX. We define LX=∑i=1t+18si×LiX=AX+BX+CX:(9)CRS=E1Aizi=1t+18,E1αAAizi=1t+18E2Bizi=1t+18,E2αBBizi=1t+18E1Cizi=1t+18,E1αCCizi=1t+18E1βLizi=1t+18,E1zi=1N,E1αBE1β,E21,E2αA,E2αB,E2αC.(2)
ProveCRS,s⟶π: P generates proof π from CRS and public private input s.P calculates E1Az, E1αAAz, E2Bz, E2αBBz, E1Cz, E1αCCz, E1βLz with ai = bi = ci:(10)E1Az=E1s1A1z+s2A2z+⋯+st+18At+18z=s1E1A1z+s2E1A2z+⋯+s1E1At+18z,E1αAAz=E1s1αAA1z+s2αAA2z+⋯+st+18αAAt+18z=s1E1αAA1z+s2E1αAA2z+⋯+s1E1αAAt+18z.The same principle forE2Bz, E2αBBz, E1Cz, E1αCCz, and E1βLz(11)πA=E1Az,πA′=E1αAAz,πB=E2Bz,πB′=E2αBBz,πC=E1Cz,πC′=E1αCCz,πL′=E1βLzπH=E1Hz,π=πA,πB,πC,πA′,πB′,πC′,πL′,πH.(3)
Verifyπ,CRS⟶Yes/No: Sv computes VKz=E2Zz by CRS and verifies the following equations; if all the equality holds, the authentication is successful, output Yes, otherwise, output No,Figure 5
The circuit C of the arithmetic equations.Verify the following equations:(12)eE1αB,πB=eE11,πB′,eπA,E2αA=eπA′,E21,eπC,E2αC=eπC′,E21,eπL′,E11=eπA+πC⋅eE1β,πB,eπA,πB=eπH,VKz⋅eπC,E21.Lines of the Equations (12) verifies whether A(z), B(z), and C(z) is a linear combination of set Aiz,Biz, and Ciz respectively; by verifying that L(z) = A(z) + B(z) + C(z) of lines of the Equations (12) holds, which shows that A(z), B(z), C(z) correspond to the same coefficient s, (5) lines of the Equations (12) is true, indicating that P(z) = H(z)Z(z).The outline of the zk-SNARK is as shown in Figure6.Figure 6
The Outline of zk-SNARK.


### 3.4. Verification

Whenn zk-SNARKs are verified, that is, n yes is output, the biometric identification is passed, the output is accepted, or the output is rejected.


## 3.1. Scheme Overview

In our construction, we divided our scheme into three stages: extract fingerprint feature points, construction of biometric identification based on zk-SNARK, and verification. Extract fingerprint feature points: first of all, we need to segment the fingerprint region from the background of the image, then we select the minutiae as the fingerprint feature points, and finally, the fingerprint feature points are represented in the plane right-angle coordinates and the feature points are sorted according to the distance from the center point. Construction of biometric identification based on zk-SNARK: the proverP constructs a ZKP on the basis of the known template and the second collected fingerprint feature points, which makes the verifier Sv believe whether the second collected fingerprint feature and the template are from the same person’s fingerprint without leaking the template. Verification: according to the proof provided by the prover and some public information CRS, the verifier verifies whether the prover is correct or not. The framework of biometric identification is described in Figure 1.Figure 1
Framework of biometric identification.


## 3.2. Extract Fingerprint Feature Points

The preprocessing of the fingerprint image goes through eight steps as shown Figure2:(1)
Fingerprint preprocessing: in the process of fingerprint preprocessing, the method in [23] is adopted. First of all, the fingerprint image is divided into 3∗3 blocks, and then the mean value and variance value are calculated in each block for segmenting the fingerprint area. Finally, enhance the fingerprint image to produce a fingerprint skeleton image. Here, the cross number method is used to extract the end points and the bifurcation points of the fingerprint features.(2)
Selection and representation of feature points: It is necessary to select the extracted feature points to avoid the situation that the extracted minutiae have many pseudominutiae (such as the edge part and the blurred part of the fingerprint image) due to the influence of external factors such as noise. For matching the input of the fuzzy extractor, the selected feature points need to be represented in an appropriate form.(i)
Selection of the center point: now, the Poincare [24] indexing algorithm is the most commonly used method to find the center point which may not be accurate enough (for example, the center area of a fingerprint is obtained instead of a specific point), but do not affect our approach, because we do not directly use it as a reference point for feature extraction or fingerprint comparison, but take the region where the central point is located as a reference and select several minutiae around the central point.(ii)
Selection of the minutiae point: we use the cross number method to detect fingerprint endpoints or bifurcations. If the selected minutiae points are too many, it will increase the verification time, if too few, the uniqueness of the fingerprint will not be obvious. So, we should select appropriate number of minutiae points to represent the characteristics of the whole fingerprint. First of all, we let the minimum sampling radiusRmin=40px (px represents picture pixels). Then, the end point of the fingerprint ridge line is selected as the reference point; after that, we establish a polar coordinate system. (0, 0) is the center point of the coordinates, and the coordinates of any minutiae point mk is ρk,θk. For any minutiae point, if it satisfies ρ>Rmin, it will be a candidate minutiae point. Meanwhile, we select the nearest 3n minutiae points closest to center point and add them to the selection queue.(iii)
Sorting of the minutiae point. The minutiae selected in the previous step are sorted from small to large inθ value. Then, a set of minutiae points mk, k∈3n is formed, in which 3n is the number of effective minutiae points selected. Mk=ρ,θk, ρ is the distance from the center point, and θk is the angle relative to the polar axis.(3)
Feature point processing: convert polar coordinatesmk, k∈3n to rectangular coordinates Mk, k∈3n as fingerprint feature points. The method is as follows: Biok=xk,yk, where xk=ρcosθk and yk=ρsinθk. We divide the 3n fingerprint feature points into n groups; 3 fingerprint feature points in each group, that is, Bioi,ji∈n, j∈1,2,3. We save Bioi,ji∈n, j∈1,2,3 as a template to the third-party security center (Figure 3). Take the same method for the second time to get Bioi,j′, i∈n, j∈1,2,3, and do not need to save Bioi,j′, i∈n, j∈1,2,3,(4)
Matching: calculate Euclidean distanceη=DisBioi,j′,Bioi,j,i∈n,j∈1,2,3, respectively. Compare the size of ηi and the threshold δ, respectively, if half of the ηi are less than or equal to δ, the authentication is passed, or the authentication is not passed. The framework of the matching is described in Figure 4.Figure 2
Eight stages of fingerprint preprocessing (original image, binarization, background separation, texture mask, texture enhancement, texture characterization, feature point calculation, and center feature extraction).Figure 3
Framework of extracting fingerprint templates.Figure 4
The outline of the matching.


## 3.3. Construction of Biometric Identification Based on Zero-Knowledge Proof

For security reasons,P can obtain the template Bioi,j, i∈n, j∈1,2,3, by obtaining the authorization of third-party security center through the private key. Bioi,ji∈n, j∈1,2,3 is kept secret Sv. That is, P can get the template Bioi,j and the fingerprint information Bioi,j′ collected for the second time. Sv only gets the fingerprint information Bioi,j′ collected for the second time. Since Bioi,j, i∈n, j∈1,2,3, is kept secret Sv, ηi=DisBioi,j′,Bioi,j,i∈n,j∈1,2,3, cannot be calculated directly, and a ZKP needs to be used.The goal of our scheme is using the idea of zk-SNARK to convince theSv that Bioi,ji∈n, j∈1,2,3 and Bioi,j′, i∈n, j∈1,2,3 satisfy the distance threshold condition ηi, i∈n is less than or equal to δ, that is, ηi∈0,δ, i∈n. P uses the following three-step strategy to prove to Sv that Bioi and Bioi′ satisfy the distance threshold condition ηi∈0,δ, i∈n. The scheme performs a total of n zk-SNARKs. Take the first group as an example to elaborate on the whole process. We suppose Bio1,j′=a1,j′,b1,j′,a2,j′,b2,j′,a3,j′,b3,j′ and Bio1,j=a1,j,b1,j,a2,j,b2,j,a3,j,b3,j, j∈1,2,3:(1)
Convert the arithmetic equations into a circuitCThe arithmetic equations:(4)∑j=13b1,j−b1,j′2+a1,j−a1,j′2=20ω0+21ω1+⋯+2tωt,ω∈0,1δ2=2t+1−1.The arithmetic equations are covered into the circuitC (Figure 5).The constraints of circuitC (it is transformed into t + 7 constraints):(5)ωiωi−1=0,i∈1,2,…,t,δ2=2t+1−1,y1,j=a1,j−a1,j′2+b1,j−b1,j′2,j∈1,2,3,η1=∑j=13y1,j,η1=20ω0+21ω1+⋯+2tωt.(2)
Convert constraints to R1CS.Lets=1,ω0,ω1,⋯,ωt,a1,j,a1,j′,b1,j,b1,j′,y1,j,η1 find the three matrices a, b, and c for each constraint s⋅a×s⋅b=s⋅c, that is t + 7 constraints, so a, b, and c are three (t + 7) × (t + 18) matrices.(3)
Convert R1CS to QAP.According to Lagrange interpolation, three polynomial matrices of degreet + 6 can be obtained.(6)AX=A1X,A2X,…,At+18X,BX=B1X,B2X,…,Bt+18X,CX=C1X,C2X,…,Ct+18X.s meets PX=s⋅AX×s⋅BX−s⋅CX=HXZX, where ZX=X−1X−2⋯X−t+7, H(X) = P(X)/Z(X).The equation holds whenX=1,2,⋯,t+7 to satisfy all constraints.We will now construct a noninteraction zero knowledge for QAP generators that outputs relations of the form:(7)R=s|s=1,ω0,ω1,…,ωt,a1,b1,j,b1,j′,y1,j,η1s⋅AX×s⋅BX=s⋅CX.The relation defines a language of witnesses and statements (public and private inputs).s=1,ω0,ω1,…,ωt,a1,j,a1,j′,b1,j,b1,j′,y1,j,η1,j∈1,2,3 such that:(8)s⋅AX×s⋅BX−s⋅CX=HXZX.(1)
SetupR←CRS: introduce third-party trusted settings to generate random numbers αA, αB, αC,β,z, which keep secret from P and Sv, and can then be discarded. For the convenience of writing, we set si=1t+18=1,ω0,ω1,…,ωt,a1,j,a1,j′,b1,j,b1,j′,y1,j,η1,j∈1,2,3. We define AX=∑i=1t+18si×AiX,BX=∑i=1t+18si×BiX,CX=∑i=1t+18si×CiX. We define LX=∑i=1t+18si×LiX=AX+BX+CX:(9)CRS=E1Aizi=1t+18,E1αAAizi=1t+18E2Bizi=1t+18,E2αBBizi=1t+18E1Cizi=1t+18,E1αCCizi=1t+18E1βLizi=1t+18,E1zi=1N,E1αBE1β,E21,E2αA,E2αB,E2αC.(2)
ProveCRS,s⟶π: P generates proof π from CRS and public private input s.P calculates E1Az, E1αAAz, E2Bz, E2αBBz, E1Cz, E1αCCz, E1βLz with ai = bi = ci:(10)E1Az=E1s1A1z+s2A2z+⋯+st+18At+18z=s1E1A1z+s2E1A2z+⋯+s1E1At+18z,E1αAAz=E1s1αAA1z+s2αAA2z+⋯+st+18αAAt+18z=s1E1αAA1z+s2E1αAA2z+⋯+s1E1αAAt+18z.The same principle forE2Bz, E2αBBz, E1Cz, E1αCCz, and E1βLz(11)πA=E1Az,πA′=E1αAAz,πB=E2Bz,πB′=E2αBBz,πC=E1Cz,πC′=E1αCCz,πL′=E1βLzπH=E1Hz,π=πA,πB,πC,πA′,πB′,πC′,πL′,πH.(3)
Verifyπ,CRS⟶Yes/No: Sv computes VKz=E2Zz by CRS and verifies the following equations; if all the equality holds, the authentication is successful, output Yes, otherwise, output No,Figure 5
The circuit C of the arithmetic equations.Verify the following equations:(12)eE1αB,πB=eE11,πB′,eπA,E2αA=eπA′,E21,eπC,E2αC=eπC′,E21,eπL′,E11=eπA+πC⋅eE1β,πB,eπA,πB=eπH,VKz⋅eπC,E21.Lines of the Equations (12) verifies whether A(z), B(z), and C(z) is a linear combination of set Aiz,Biz, and Ciz respectively; by verifying that L(z) = A(z) + B(z) + C(z) of lines of the Equations (12) holds, which shows that A(z), B(z), C(z) correspond to the same coefficient s, (5) lines of the Equations (12) is true, indicating that P(z) = H(z)Z(z).The outline of the zk-SNARK is as shown in Figure6.Figure 6
The Outline of zk-SNARK.


## 3.4. Verification

Whenn zk-SNARKs are verified, that is, n yes is output, the biometric identification is passed, the output is accepted, or the output is rejected.


## 4. Security Description and Performance Analysis

### 4.1. Security Description

According to Schwartz-Zippel lemma [25], we randomly choose a random number substituted into equations (1)–(3); when we verify the equations hold, we say that the equations are permanent true.SNARK-completeness: it assures a verifier always accepts an proof generated by an honest prover. The polynomials of the QAP are generated (Algorithm 1). The prover knows a secrets input and he needs to find a valid distribution for all the gates of the arithmetic circuit C. The prover constructs P(X), divides it by Z(X), and encodes the result using the proving key (Algorithm 2).Algorithm 1: The phase of key generation.
Key generation (input arithmetic circuitC)(1)
Construct the QAPQC=A,B,C,ZofC(2)
Randomly samplez∈F(3)
Generate the proving key:Az=A1z,A2z,…,At+18zBz=B1z,B2z,…,Bt+18zCz=C1z,C2z,…,Ct+18zHz=s⋅Az×s⋅Bz−s⋅Cz/Zz(4)
Generate the Verification KeyVKz=E2ZzOutput CRSAlgorithm 2: The phase of prover.
Prover (input: CRS,s∈F)(1)
Construct the QAP:QAPC=A,B,C,ZofC(2)
Compute a valid distribution s=1,ω0,ω1,…,ωt,a1,j,a1,j′,b1,j,b1,j′,y1,j,η1,such thatPX=s⋅AX×s⋅BX−s⋅CX(3)
Determine the coefficienthii=0d of HX=s⋅Az×s⋅Bz−s⋅Cz/ZX(4)
Construct the proofπ:=πA,πB,πC,πH, whereπA:=aiE1Aizi=1t+18, πB:=biE1Bizi=1t+18πC:=ciE1Cizi=1t+18, πH:=E1Hz,OutputπFor example,πH:=E1Hz means that πH is the encoded polynomial H(z) in the group G1. The verifier checks whether Z(X) divides P(X) (Algorithm 3). The verifying equation eπA,πB=eπH,VKz⋅eπC,E21 is equivalent to eg1,g2s⋅Az×s⋅Bz=eg1,g2s⋅Cz+HZZz. So, the nondegeneracy of the pairing e implies the equation eπA,πB=eπH,VKz⋅eπC,E21 hold if and only if P(z) = H(z)Z(z). If the proof was constructed honestly, and so equation eπA,πB=eπH,VKz⋅eπC,E21 holds which shows completeness. In other words, if P knows s, that is, P knows Bio1,j,j=1,2,3, it must pass the verification.Algorithm 3: The phase of verifier.
Verifier (input: CRS, proofπ)(1)
CalculateVKz=E2Zz(2)
Check QAP divisibility:eπA,πB=eπH,VKz⋅eπC,E21Output Yes (correct)/No (incorrect)SNARK-soundness: A malicious prover could useP(X) = Z(X) for his proof with A(X) = 1, B(X) = Z(X), and C(X) = 0. It would return Yes by the verifier, although the prover does not know the secret s. Therefore, the verifier must check twice to ensure that P(X) was built correctly. In other words, if the verification is passed, P must know s, that is, P must know Bio1,j,j=1,2,3:(1)
Correct span: the polynomialsAiX, BiX, and CiX are linear combinations of ai, bi, and ci, respectively(2)
Same coefficients: the same coefficientssi are used by the linear combinations AiX, BiX, and CiXIt is achieved by requiring the prover to construct the same proof for the second time, but using proving keys which are different from the first ones by multiplying a random constant (Table2).Table 2
Key generation extras.
Correct span checkSame coefficient check(1) Randomly sampleαA,αB,αC,∈F(1) Randomly sampleβ∈F(2) Proving key:(2) Proving key:πA′=ai∗E1αAAizi=1t+18,πL′=E1βLz=E1si∗E1βLizi=1t+18,πB′=bi∗E1αBBizi=1t+18,(3) Verification keyπC′=ci∗E1αCCizi=1t+18,Lz=Az+Bz+Cz,(3) Verification key:That is,αA=αB=αC=siαAπA=πA′, αBπB=πB′, αCπC=πC′Correct span check: the prover has to addπA′=∑i=1t+18ai×Ai′z, πB′=∑i=1t+18ai×Bi′z, and πC′=∑i=1t+18ai×Ci′z to the proof π. The verifier can use the proof to check whether(13)eE1αB,πB=eE11,πB′,eπA,E2αA=eπA′,E21,eπC,E2αC=eπC′,E21.Since for exampleeπA,E2αA=eπA′,E21 holds if and only if πA′=αAπA′. Based on the knowledge of exponent [26] assumption, there is a very high probability that the prover used the encoded version AiX and Ai′X.Same coefficient check: the prover has to add to the proofπL:=∑i=1nsiLiz,BX which the verifier uses to check whether eπL′,E11=eπA+πC⋅eE1β,πB.Similarly, the prover used the same coefficientsπA, πB, and πC if the equation holds.Since correct span and same coefficients guarantee that the prover constructed the polynomialP(X) correctly, the divisibility check means that the probability of the prover knowing the secret s is extremely high.Zero knowledge: in the whole process, the supervisorSv cannot extract any knowledge of Bioi,j, i∈n,j∈1,2,3.


### 4.2. Performance Properties

Our experiment has two purposes: (i) Evaluating the performance of our scheme using the method described in Section 3 and observe how the size of the threshold and the number of fingerprint features extracted affects accuracy and false rejection rate (FRR). (ii) Measuring the execution times of each phase of our authentication scheme:(1)
Experimental setup: in this paper, Python language was used to test the performance and the time of the scheme in the MAC environment. The MAC used in the experiment is configured as 1.8 GHz Intel Core i5, and the memory is 8 GB and 1600 MHz DDR3. The fingerprint database we use was FVC2002 DB1_B/101 and DB1_B/102 [26]. The database contains 2 fingers, each finger has 8 different fingerprint images, each person’s fingerprint has A82=56 positive samples, so the positive samples have 2∗56 = 112 groups, while the antagonistic samples have 8∗8∗2 = 128 groups. All computations in the scheme is carried out on the finite field Fp with(14)p=0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001,αA=G1Fp690,αB=G1Fp1578,αC=G1Fp912,β=G1Fp16218178020,γ=G1Fp1820222,z=z=Fp44298242404171008400611305470227805003354843506687190111965214616867353735779.Taking one of the fingerprints as an example, the extracted fingerprint coordinates are shown in Figure7. Figure 8 is the coefficients of the polynomials of QAP, which is only partially presented because of the limited space and the proofs sent by P to Sv.(2)
Evaluation of the performance: in the following, we discuss the experimental evaluation of the performance, in terms of accuracy and FRR.We did the experiment by varying the size of the threshold and the number of fingerprint features extracted. In this experiment, we tested 128 + 112 = 240 groups of experiments for each threshold with varying size as25−1,26−1,⋯,220−1 and also tested 128 + 112 = 240 groups of experiments for each fingerprint feature with varying number as 9, 12, 15, …, 54. Accuracy and FAR results are reported in Tables 3 and 4 and in Figures 9 and 10.According to the experimental results, the accuracy and FRR does not change with the number of fingerprint features. The reason is that our threshold increases exponentially, so the accuracy and FRR has little to do with the number of fingerprint features. So, we only discuss the relationship between the accuracy, the FRR and the distance threshold here. Accuracy increases with the increasing of the distance threshold. In contrast, FRR decreases with the increasing number of the distance threshold. Therefore, depending on the security and usability trade-off requirement of a particular application, we select the appropriate ratio between accuracy and FRR. Because our distance threshold must be set to2n−1, which changes exponentially, the growth rate is too large to find a more suitable distance threshold, so the experimental results are not very good. In the later stage, we will design a new protocol on this basis, and there is no restriction on the threshold, that is, the threshold can be any value and then conduct further research.(3)
The execution times of each phase: we extracted 9, 15, 18, …, 54 fingerprint features, respectively. The time consumption of each stage of the whole scheme is shown in Table4. Figure 11 shows the time consumption of various stages in the entire project process since the time consumption of each stage varies greatly. Figure 12 specifically shows some of the stages that consume less time in the scheme.Table 3
Variation of accuracy with the size of threshold.
δ2Positive sampleAntagonistic sampleAccuracy25−1112128026−1112128027−1112128028−1112128029−11121280210−11121280211−11121280212−11121280.01786213−11121280.08929214−11121280.4464215−11121280.8393216−11121281217−11121281218−11121281219−11121281220−11121281Table 4
Variation of FRR with the size of threshold.
δ2Positive sampleAntagonistic sampleAccuracy25−1112128126−1112128127−1112128128−1112128129−11121281210−11121281211−11121281212−11121281213−11121280.875214−11121280.4688215−11121280.09375216−11121281217−11121281218−11121281219−11121281220−11121281Figure 7
The extracted fingerprint feature points.Figure 8
The coefficients of the polynomials of OAP and the proof.Figure 9
Variation of accuracy with the size of threshold.Figure 10
Variation of FRR with the size of threshold.Figure 11
The time overhead of each stage.Figure 12
Time consumption of the part stage.Accordingly, the setup time proof time, CRS time, R1CS time, and verify time of the scheme are very small, and the efficiency of these stages is also relatively high. Figure12 makes it clearer to discount the time consumption of these stages. The QAP stage is the most time-consuming in the whole scheme (Table 5), the scheme groups fingerprints, which greatly improves efficiency, and the efficiency will also be greatly improved by optimizing parallelism in the later stage. The setup time is the total time for fingerprint information preprocessing establishment. As the number of fingerprint features increases, the setup time and proof time show an approximately linear increase (Figures 11 and 12).Table 5
The time overhead of each stage.
Number of fingerprintsTotal time (ms)QAP time (ms)R1CS time (ms)CRS time (ms)Setup time (ms)Proof time (ms)Verification time (ms)93980.683826.850.4977.7626.7946.921.82125261.25064.380.69101.4634.2258.132.29156658.126404.700.89132.6343.3373.513.01188124.657806.351.06163.0853.8096.703.61219358.869007.171.32182.2060.96103.064.102410840.3610427.121.41212.3571.79122.704.942712180.6411723.861.53241.6879.24128.855.423013526.8413021.141.72262.4389.12146.445.943314961.614416.801.94286.2095.93154.316.383616386.4515746.572.13348.76106.71174.847.383917728.2017062.652.26355.02111.80188.857.534218923.4618220.742.53362.43125.93203.678.494522790.5621939.8482.99456.59144.48237.359.254825487.3824514.517.75521.12150.44274.2319.285126948.84425927.627.94528.37168.24295.1321.485428788.2327683.263.62571.81186.95318.7723.78


## 4.1. Security Description

According to Schwartz-Zippel lemma [25], we randomly choose a random number substituted into equations (1)–(3); when we verify the equations hold, we say that the equations are permanent true.SNARK-completeness: it assures a verifier always accepts an proof generated by an honest prover. The polynomials of the QAP are generated (Algorithm 1). The prover knows a secrets input and he needs to find a valid distribution for all the gates of the arithmetic circuit C. The prover constructs P(X), divides it by Z(X), and encodes the result using the proving key (Algorithm 2).Algorithm 1: The phase of key generation.
Key generation (input arithmetic circuitC)(1)
Construct the QAPQC=A,B,C,ZofC(2)
Randomly samplez∈F(3)
Generate the proving key:Az=A1z,A2z,…,At+18zBz=B1z,B2z,…,Bt+18zCz=C1z,C2z,…,Ct+18zHz=s⋅Az×s⋅Bz−s⋅Cz/Zz(4)
Generate the Verification KeyVKz=E2ZzOutput CRSAlgorithm 2: The phase of prover.
Prover (input: CRS,s∈F)(1)
Construct the QAP:QAPC=A,B,C,ZofC(2)
Compute a valid distribution s=1,ω0,ω1,…,ωt,a1,j,a1,j′,b1,j,b1,j′,y1,j,η1,such thatPX=s⋅AX×s⋅BX−s⋅CX(3)
Determine the coefficienthii=0d of HX=s⋅Az×s⋅Bz−s⋅Cz/ZX(4)
Construct the proofπ:=πA,πB,πC,πH, whereπA:=aiE1Aizi=1t+18, πB:=biE1Bizi=1t+18πC:=ciE1Cizi=1t+18, πH:=E1Hz,OutputπFor example,πH:=E1Hz means that πH is the encoded polynomial H(z) in the group G1. The verifier checks whether Z(X) divides P(X) (Algorithm 3). The verifying equation eπA,πB=eπH,VKz⋅eπC,E21 is equivalent to eg1,g2s⋅Az×s⋅Bz=eg1,g2s⋅Cz+HZZz. So, the nondegeneracy of the pairing e implies the equation eπA,πB=eπH,VKz⋅eπC,E21 hold if and only if P(z) = H(z)Z(z). If the proof was constructed honestly, and so equation eπA,πB=eπH,VKz⋅eπC,E21 holds which shows completeness. In other words, if P knows s, that is, P knows Bio1,j,j=1,2,3, it must pass the verification.Algorithm 3: The phase of verifier.
Verifier (input: CRS, proofπ)(1)
CalculateVKz=E2Zz(2)
Check QAP divisibility:eπA,πB=eπH,VKz⋅eπC,E21Output Yes (correct)/No (incorrect)SNARK-soundness: A malicious prover could useP(X) = Z(X) for his proof with A(X) = 1, B(X) = Z(X), and C(X) = 0. It would return Yes by the verifier, although the prover does not know the secret s. Therefore, the verifier must check twice to ensure that P(X) was built correctly. In other words, if the verification is passed, P must know s, that is, P must know Bio1,j,j=1,2,3:(1)
Correct span: the polynomialsAiX, BiX, and CiX are linear combinations of ai, bi, and ci, respectively(2)
Same coefficients: the same coefficientssi are used by the linear combinations AiX, BiX, and CiXIt is achieved by requiring the prover to construct the same proof for the second time, but using proving keys which are different from the first ones by multiplying a random constant (Table2).Table 2
Key generation extras.
Correct span checkSame coefficient check(1) Randomly sampleαA,αB,αC,∈F(1) Randomly sampleβ∈F(2) Proving key:(2) Proving key:πA′=ai∗E1αAAizi=1t+18,πL′=E1βLz=E1si∗E1βLizi=1t+18,πB′=bi∗E1αBBizi=1t+18,(3) Verification keyπC′=ci∗E1αCCizi=1t+18,Lz=Az+Bz+Cz,(3) Verification key:That is,αA=αB=αC=siαAπA=πA′, αBπB=πB′, αCπC=πC′Correct span check: the prover has to addπA′=∑i=1t+18ai×Ai′z, πB′=∑i=1t+18ai×Bi′z, and πC′=∑i=1t+18ai×Ci′z to the proof π. The verifier can use the proof to check whether(13)eE1αB,πB=eE11,πB′,eπA,E2αA=eπA′,E21,eπC,E2αC=eπC′,E21.Since for exampleeπA,E2αA=eπA′,E21 holds if and only if πA′=αAπA′. Based on the knowledge of exponent [26] assumption, there is a very high probability that the prover used the encoded version AiX and Ai′X.Same coefficient check: the prover has to add to the proofπL:=∑i=1nsiLiz,BX which the verifier uses to check whether eπL′,E11=eπA+πC⋅eE1β,πB.Similarly, the prover used the same coefficientsπA, πB, and πC if the equation holds.Since correct span and same coefficients guarantee that the prover constructed the polynomialP(X) correctly, the divisibility check means that the probability of the prover knowing the secret s is extremely high.Zero knowledge: in the whole process, the supervisorSv cannot extract any knowledge of Bioi,j, i∈n,j∈1,2,3.


## 4.2. Performance Properties

Our experiment has two purposes: (i) Evaluating the performance of our scheme using the method described in Section 3 and observe how the size of the threshold and the number of fingerprint features extracted affects accuracy and false rejection rate (FRR). (ii) Measuring the execution times of each phase of our authentication scheme:(1)
Experimental setup: in this paper, Python language was used to test the performance and the time of the scheme in the MAC environment. The MAC used in the experiment is configured as 1.8 GHz Intel Core i5, and the memory is 8 GB and 1600 MHz DDR3. The fingerprint database we use was FVC2002 DB1_B/101 and DB1_B/102 [26]. The database contains 2 fingers, each finger has 8 different fingerprint images, each person’s fingerprint has A82=56 positive samples, so the positive samples have 2∗56 = 112 groups, while the antagonistic samples have 8∗8∗2 = 128 groups. All computations in the scheme is carried out on the finite field Fp with(14)p=0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001,αA=G1Fp690,αB=G1Fp1578,αC=G1Fp912,β=G1Fp16218178020,γ=G1Fp1820222,z=z=Fp44298242404171008400611305470227805003354843506687190111965214616867353735779.Taking one of the fingerprints as an example, the extracted fingerprint coordinates are shown in Figure7. Figure 8 is the coefficients of the polynomials of QAP, which is only partially presented because of the limited space and the proofs sent by P to Sv.(2)
Evaluation of the performance: in the following, we discuss the experimental evaluation of the performance, in terms of accuracy and FRR.We did the experiment by varying the size of the threshold and the number of fingerprint features extracted. In this experiment, we tested 128 + 112 = 240 groups of experiments for each threshold with varying size as25−1,26−1,⋯,220−1 and also tested 128 + 112 = 240 groups of experiments for each fingerprint feature with varying number as 9, 12, 15, …, 54. Accuracy and FAR results are reported in Tables 3 and 4 and in Figures 9 and 10.According to the experimental results, the accuracy and FRR does not change with the number of fingerprint features. The reason is that our threshold increases exponentially, so the accuracy and FRR has little to do with the number of fingerprint features. So, we only discuss the relationship between the accuracy, the FRR and the distance threshold here. Accuracy increases with the increasing of the distance threshold. In contrast, FRR decreases with the increasing number of the distance threshold. Therefore, depending on the security and usability trade-off requirement of a particular application, we select the appropriate ratio between accuracy and FRR. Because our distance threshold must be set to2n−1, which changes exponentially, the growth rate is too large to find a more suitable distance threshold, so the experimental results are not very good. In the later stage, we will design a new protocol on this basis, and there is no restriction on the threshold, that is, the threshold can be any value and then conduct further research.(3)
The execution times of each phase: we extracted 9, 15, 18, …, 54 fingerprint features, respectively. The time consumption of each stage of the whole scheme is shown in Table4. Figure 11 shows the time consumption of various stages in the entire project process since the time consumption of each stage varies greatly. Figure 12 specifically shows some of the stages that consume less time in the scheme.Table 3
Variation of accuracy with the size of threshold.
δ2Positive sampleAntagonistic sampleAccuracy25−1112128026−1112128027−1112128028−1112128029−11121280210−11121280211−11121280212−11121280.01786213−11121280.08929214−11121280.4464215−11121280.8393216−11121281217−11121281218−11121281219−11121281220−11121281Table 4
Variation of FRR with the size of threshold.
δ2Positive sampleAntagonistic sampleAccuracy25−1112128126−1112128127−1112128128−1112128129−11121281210−11121281211−11121281212−11121281213−11121280.875214−11121280.4688215−11121280.09375216−11121281217−11121281218−11121281219−11121281220−11121281Figure 7
The extracted fingerprint feature points.Figure 8
The coefficients of the polynomials of OAP and the proof.Figure 9
Variation of accuracy with the size of threshold.Figure 10
Variation of FRR with the size of threshold.Figure 11
The time overhead of each stage.Figure 12
Time consumption of the part stage.Accordingly, the setup time proof time, CRS time, R1CS time, and verify time of the scheme are very small, and the efficiency of these stages is also relatively high. Figure12 makes it clearer to discount the time consumption of these stages. The QAP stage is the most time-consuming in the whole scheme (Table 5), the scheme groups fingerprints, which greatly improves efficiency, and the efficiency will also be greatly improved by optimizing parallelism in the later stage. The setup time is the total time for fingerprint information preprocessing establishment. As the number of fingerprint features increases, the setup time and proof time show an approximately linear increase (Figures 11 and 12).Table 5
The time overhead of each stage.
Number of fingerprintsTotal time (ms)QAP time (ms)R1CS time (ms)CRS time (ms)Setup time (ms)Proof time (ms)Verification time (ms)93980.683826.850.4977.7626.7946.921.82125261.25064.380.69101.4634.2258.132.29156658.126404.700.89132.6343.3373.513.01188124.657806.351.06163.0853.8096.703.61219358.869007.171.32182.2060.96103.064.102410840.3610427.121.41212.3571.79122.704.942712180.6411723.861.53241.6879.24128.855.423013526.8413021.141.72262.4389.12146.445.943314961.614416.801.94286.2095.93154.316.383616386.4515746.572.13348.76106.71174.847.383917728.2017062.652.26355.02111.80188.857.534218923.4618220.742.53362.43125.93203.678.494522790.5621939.8482.99456.59144.48237.359.254825487.3824514.517.75521.12150.44274.2319.285126948.84425927.627.94528.37168.24295.1321.485428788.2327683.263.62571.81186.95318.7723.78


## 5. Conclusion

We propose a novel biometric identification scheme based on zk-SNARK. In the scheme, the biometric information and templates are entered into the equation as private input, and the Euclidean distance of the two biological features is expressed in binary form based on the size of the threshold and then transform the problem into a polynomial domain to improve efficiency. Compared with the general biometric identification scheme, our scheme not only greatly improves the efficiency but also has the function of privacy protection, which can protect the fingerprint template from disclosure. We have implemented the proposed authentication solution on a public data set of fingerprint images and evaluated the performance and security and calculated the proof time, verification time, R1CS time, QAP time, and certificate time consumption of each stage corresponding to the number of different fingerprint features, which will surely produce more and more important and far-reaching impact in the digital economy and other fields.In our future work, we will (1) design new protocols on this basis, and there is no restriction on the threshold, that is, the threshold can be any value, and then conduct further research and (2) improve the efficiency of the scheme and reduce QAP time. (3) This solution does not design an application scenario, and we will focus on it in the next step.



---

*Source: 2791058-2022-09-13.xml*