Privacy Data Management Mechanism Based on Blockchain and Federated Learning

1  Introduction

With the accelerating process of digitization of medical systems in various countries, medical data shows an exponential upward trend [1]. Therefore, the fields of public medical management, online patient access and medical data management have become the research topics in academic and medical circles. The Internet has largely improved the traditional pattern of medical interrogation, thus forming a medical network community dominated by patients, research institutions and medical institutions. The community is conducive to alleviating the contradiction between patients and society. Different measures taken by relevant industries in various countries have proved this situation to a certain extent. In Estonia [2], a digital medical infrastructure was created to form a healthy community network of citizens and health care stakeholders (providers, insurance companies, etc.). Through this way, it is of great significance to study the reform of medical model under the new situation. The recent 2019 New Coronavirus (also known as 2019-nCoV and COVID-2019) pandemic also demonstrated the necessity to establish a medical network community. Through the management of patient medical data in various countries, research institutions can conduct data visual analysis based on big data [3], and provide government and other-decision-making institutions with real-time research and judgment and make these institutions able to predict the epidemic situation, which greatly reduces the momentum of public panic about the epidemic situation [4].

In the medical network community, the patient’s personal information data and condition information will be recorded to form big data [5]. Big data has been applied in many fields and plays a particularly critical role in the decision-making process of many hospital institutions [6]. For the security needs of data management, medical institutions have the responsibility to take confidentiality measures for patients’ private data [7,8]. If being leaked, this information may be biased. FL keeps all sensitive data in the local organization to which the data belongs, which makes it possible to combine fragmented medical data sources with privacy protection. Although the training method of FL exchanging model parameters without exchanging specific data can effectively protect users’ privacy, FL still faces some security risks. In the training process of FL model, though the local original data of each user will not be disclosed, but it still have limitation that if there are ‘dishonest’, ‘honest and curious’ servers or malicious clients, the user’s local data information may still be deduced from the updated model parameters, that is, reasoning attack, poisoning attack and attack of Generative Adversarial Networks (GAN) and other types of attacks [9]. Therefore, the privacy protection ability of important data under FL environment is insufficient.

Security and privacy of data management are priorities [10]. In order to make up for the lack of privacy protection of important data in FL, we use KH-PKE scheme to hide patient data information and data sources. At the same time, FL algorithms can reduce the frequency of data communication and reduce the risk of exposing patient data. Therefore, when considering data security, we use the smart contract system based on the above-mentioned KH-PKE solution instead of the joint server to realize that medical data can be uploaded to the CB and realize the automatic sharing of medical data. In each round of federation, smart contracts collect data from medical and research institutions and return aggregated parameters for all parties to automatically update the Machine Learning model. In view of the openness and distributed execution of smart contracts, all parties can also verify the correct execution of the steps in an open manner at any time. The goal is to construct a zero-knowledge proof scheme for lightweight devices under FL without excessively increasing the scale of proof, so as to realize medical data management. It hides the addresses of the sender and receiver to achieve anonymity and privacy protection. In non-interactive zero knowledge (NIZK), the dynamic group signature scheme based on CCA anonymity we used makes the NIZK scheme more secure and efficient in computing and communication cost. In the end, we combined theory and practice to analyze, and simulated and implemented the program on a personal computer.

We organize the rest of this article as follows. The second section introduces the related work, and the third section mainly constructs the data security management framework of medical network community based on CB and FL. The fourth section mainly introduces the data security sharing mechanism of medical network community based on smart contract. The fifth section mainly constructs the data privacy protection mechanism based on FL and CB and compares it with the previous schemes. The sixth section is the conclusions of this paper.

2  Related Work

2.1 Data Management in Consortium Blockchain

The ideal medical data management scheme should meet the following basic requirements, namely security and privacy protection [11], data access [12], access control and unified standards [13]. Therefore, the scheme proposed in this paper should meet the following requirements.

1.    Security and privacy protection: no one may illegally use medical data. The program should be able to ensure that the data resists illegal attacks.

2.    Data access: after obtaining the authorization, the research institution can view all relevant medical records, and the research institution can access the previous medical information under the authorization of the medical institution.

3.    Access control: only medical institutions can manage patient data, that is, no one can obtain historical data without the consent of the medical institution.

4.    Unified standards: unified data management standards should be adopted in the model to balance the overall stability of the system.

2.2 Data Management in the Consortium Blockchain with Federated Learning

The powerful, robust, flexible and secure functions of FL data cognition is helpful to solve the problem of the reliability, security, privacy protection of CB data management and optimize the storage data cost of blockchain data sharing.

Providing a trusted mechanism for all participants of FL through blockchain. The parameters of the FL model can be stored in the blockchain to ensure its security and reliability. FL has the characteristics of distributed intelligence and data privacy protection. It combines with the CB to complement each other’s advantages and improve the overall security of the system.

Some researchers use blockchain as a secure distributed ledger, which provides a potential solution for cross system management of medical information. Li et al. [14] constructed a privacy data storage protocol based on elliptic curve using ring signature to ensure data security and user identity privacy in blockchain applications. Omar et al. [15] proposed a patient-centered medical data management system medical chain, which realized privacy protection based on blockchain. Liu et al. [16] proposed a privacy protection electronic medical records management scheme based on blockchain. The original data is stored in the cloud environment, and the data index is retained in the CB to reduce the risk of disclosure [17]. However, the above scheme is not suitable for the confidentiality and constantly updated data requirements in our system.

3  Data Security Management Framework of Medical Network Community

3.1 Privacy Data Protection in Federated Learning

In the process of FL model training, the user’s local data information may still be deduced from the updated model parameters by reasoning attack, and may also be subject to poisoning attack, and attack of GAN and other types of attacks. At the same time, FL does not detect and verify the participants. Malicious participants may attack and destroy the FL training process by providing false model parameters, resulting in training failure. Therefore, the privacy protection ability of important data in FL is insufficient.

In the medical network community, data security is the premise of medical big data management. FL’s common privacy protection technologies, such as secure multi-party computing and differential privacy, are not enough to ensure data security [18,19]. At the same time, if privacy data was leaked, it would cause serious harm to patients. However, the development trend of medical big data is sharing and opening. Therefore, we should strengthen the ability of privacy protection in FL on the premise of ensuring the effective sharing of training data among participants, so as to give full play to the value of data management.

In order to make up for the lack of privacy protection of important data in FL, a zero-knowledge proof scheme suitable for lightweight devices is constructed to realize medical data management. In NIZK scheme, CCA anonymous dynamic group signature mechanism [20] is more secure and efficient in computing and communication cost. The signature mechanism can be used in the CB to provide unlinkability and anonymity, so as to improve the ability of data management and privacy protection in the medical CB. At the same time, in order to consider the security of private data, a smart contract system for the safe sharing of medical data is constructed based on the KH-PKE scheme to realize that the medical data hidden and stored in medical institutions and research institutions are stored on the CB for automatic data sharing operation to meet the needs of more High privacy requirements.

3.2 Medical Network Community Based on Consortium Blockchain and Federated Learning

Consortium Blockchain network: as a part of the blockchain [21], the CB has more advantages in efficiency and flexibility than the public blockchain, and can provide better privacy protection. It uses the distributed and tamper proof characteristics of blockchain to realize the secure storage and sharing of medical and health data and reduce the management cost. as shown in Fig. 1.

Figure 1: Medical network community framework based on Consortium Blockchain and Federated learning

Federated learning network: providing a trusted mechanism for all participants of federated learning through CB. On an artificial neural network predictive model (ANN) [22], use weight parameters and biases to train medical data and upload the trained data to a smart contract for data sharing. Keeping medical data on the blockchain throughout the data sharing environment. At the same time, the global model is stored and shared using the blockchain, thus avoiding a potential single point of failure on a central server.

Entity: including research institutions and medical institutions. The mechanism of KH-PKE scheme is used to directly store ciphertext and perform some calculations on the FL and blockchain. There is no need to make any change to the FL and CB itself, so as to provide confidentiality and privacy protection in the process of data management between research institutions and medical institutions.

4  Data Security Sharing Mechanism of Medical Network Community

CB can provide technical support for the security protocol and training method of FL algorithm. After the data of medical institutions are encrypted by the mechanism of KH-PKE scheme, the local model parameters are calculated by FL. Finally, upload the data to the smart contract, aggregate different data information and return the results. At the same time, smart contracts can also resist poisoning attacks and improve the security of private data.

In the medical network community, in order to consider the security of private data, public key encryption schemes are usually used to hide medical data. However, the fact that homomorphic public key encryption schemes are vulnerable to (adaptive) ciphertext selection attacks has been ignored to some extent. Theoretically, the adversary sends a homomorphic evaluation challenge ciphertext to the decryption oracle, and can immediately destroy the security. Therefore, we use the KH-PKE scheme to hide medical privacy data to meet higher privacy requirements. Homomorphic encryption scheme can only achieve indistinguishable encryptions under chosen plaintext attack security. Our KH-PKE scheme evaluates the secret key by controlling the homomorphic operation function and achieves stronger security than indistinguishable encryptions under chosen ciphertext attack(IND-CCA1) and is as close to indistinguishable encryptions under adaptive chosen ciphertext attack(IND-CCA2) as possible. Then, the structure is described under the secure under the decision linear(DLIN) assumption, and its security proof is given.

Definition 1 (KH-PKE): let M be a message space and ⊙ be a binary operation on M. We require that for all m1,m2,m3∈M, m1⊙m2⊙m3∈M. The KH-PKE scheme (Gen, Enc, Dec, Eval) for homomorphic operation ⊙ consists of the following four algorithms:

Gen:The secret key generation algorithm takes the security parameter n∈N as the input and selects h←$G,γ,α1,α2←$Zp: output public key gpk= (X1=gγ,X2=gα1,X3=gα2,g,h), decrypt secret key gsk=(x,y)and homomorphic operation secret key skh.

Enc:The encryption algorithm takes gpk and a message m∈M as input to calculate C1=X1r,C2=X2s,C3=gr+s⋅hm, and output C=(C1,C2,C3), where r,s←$Zp represents the randomness of Enc use.

Dec:The decryption algorithm takes gsk and C as inputs, parses C into a tuple (C1,C2,C3), and calculates hm=C3/(C11x⋅C21y). If the plaintext space is small, the message m=loghhm can be obtained effectively and m or ⊥ can be output.

Eval:The evaluation algorithm adopts skh. Three ciphertext C1,C2,C3 as input, output ciphertext C or ⊥.

So far, the above KH-PKE scheme does not realize the homomorphic attribute, but the homomorphic function is reflected in the correctness defined below. Let gpk be the public key generated by Gen algorithm, Cgpk,m is all ciphertext sets of m∈M under the public key gpk,that is, Cgpk,m={C|∃r∈{0,1}∗s.t.C=Enc(gpk,m;r)}.

Definition 2 (correctness). For all (gpk,gsk,skh)←Gen(1n), the following two conditions are met: (1) For all m∈M, and all C∈Cgpk,m,Dec(gsk,C)=M. (2) For all m1,m2,m3∈M, all C1∈Cgpk,m1,C2∈Cgpk,m2, C3∈Cgpk,m3, Eval(skh,C1,C2,C3)∈Cgpk,m1⊙m2⊙m3.

Definition 3 (KH-CCA Security). a KH-PKE scheme is considered to meet KH-CCA security if for any PPT adversary A:

AdvKH−PKEKH−CCA(n)=|Pr[(gpk,gsk,skh)←Gen(1n);(m0∗,m1∗,State)←AO(find,gpk);β←${0,1};C∗←Enc(gpk,mβ∗);β′←AO(guess,State,C∗);β=β′]−12|(1)

It can be ignored in n, where O is composed of three oracle machines Eval(skh,⋅,⋅),RevHK and Dec(sk,⋅). Let D be a list and set toD={C∗} after the challenge stage (D is set to Ø in the search stage).

•   Evaluate oracle Eval(skh,⋅,⋅): if RevHK has been queried before, the oracle is unavailable. Otherwise, the oracle responds to the query (C1,C2,C3) with the result of C←Eval(skh,C1,C2,C3). In addition, if C ≠ ⊥ and C1∈D,C2∈D or C3∈D, the oracle updates the list through D←D∪{C}.

•   Homomorphic key disclosures oracleRevHK: according to the request, the oracle machine uses skh responses. (this oracle is only available once.)

•   Decryption prophecy Dec(gsk,⋅): if A queries RevHK and A obtains the challenge ciphertext C∗, the oracle is unavailable. Otherwise, the oracle will respond to the query. If C∉D, the result of C is Dec(gsk,⋅), otherwise ⊥ is returned.

•   Lemma 1. Under the DLIN assumption , the above KH-PKE scheme meets the IND-CCA1 security.

Proof. Suppose that the effective adversary A destroys the KH-KHE scheme in the sense of KH-CCA with a non-negligible probability poly(n) and gives a tuple u,v,g,s1=ur,s2=vs,s3. Decide whether to s3=gr+s, we can construct a reduction algorithm B attacking KH-CCA security to break the DLIN assumption, as follows:

               Algorithm BA(u,v,g,s1,s2,s3):

              Select h←$G, set gpk=(u,v,g,h);

                B←gpk;RevHK←skh;

                 Input (gpk,skh),run A;

When A sends ciphertext C as the decryption query, B forwards C as the decryption query of B.

(m0∗,m1∗)←AO(find,gpk);

         Sampling β←${0,1}, and then set C∗=(s1,s2,s3⋅hmβ);

β′←AO(guess,State,C∗);

               If β=β′, returns 1;

               Otherwise, returns 0.

•   If s3=gr+s, then the probability of B = 1 is the probability of A correctly guessing the hidden bit, poly(n)+12.

•   If s3 is the random element in G, then s3⋅hmb is evenly distributed in G, irrelevant to β, so the probability of A’s correct answer is 12.

Therefore, the probability of B distinguishes the distributions {u,v,g,ur,vs,gr+s} and {u,v,g,ur,vs,ρ} is equal to poly(n). This is a non-negligible probability, which contradicts the DLIN assumption. This means that if the scheme meets KH-CCA security, then the scheme meets IND-CCA1 security.

In the medical network community environment, assuming that A and B want to share medical data, they will publish a medical data sharing information on the medical CB, which is basically written as follows. The medical data ciphertext t of medical institution A is shared with research institution B, then σ is t’s signature. Then, the consortium chain first verifies whether the signature is correct, that is, whether there is medical data t in A. If so, the data sharing operation will be carried out and the behavior will be published on the CB, otherwise the behavior will be ignored. as shown in Fig. 2.

Figure 2: Data security sharing of medical network community based on smart contract

In the above data sharing process, we can all know the medical data t shared from A to B (that is, the privacy of the shared medical data t is not guaranteed). Therefore, in Section 5, this paper introduces a data privacy protection scheme based on FL and CB, which is used to prove the security of medical data t under data sharing operation.

5  Data Privacy Protection Mechanism Based on Federated Learning and Blockchain

This section constructs an efficient NIZK scheme. The scheme first constructs a Σ-Protocols [23], and then use the Fiat-Shamir heuristic method to construct the NIZK protocol in the FL environment. Finally, the NIZK scheme for complete lightweight devices is obtained by using the set member proof protocol. At the same time, CCA anonymous dynamic group signature mechanism is introduced, which greatly improves the time efficiency of generating proof. The signature mechanism is more secure and efficient in computing and communication cost under the data security management framework of medical network community [24], based on CB and FL. At the same time, the NIZK scheme is used to realize the security sharing of medical data, and verify the correctness of medical data under the sharing operation on the smart contract. Below, we will construct the design details of a zero-knowledge proof scheme suitable for FL.

5.1 Preliminary Preparation

NIZK parameters have certifier A and verifier B. Suppose the plaintext space is(0,2L), where L=u×l. First introduce the CCA anonymous dynamic group signature mechanism, and set the algorithms Setup and Partylnitial respectively:

Setup. Generate a bilinear group [25] (p,G,GT,e,g)←Gbp(1n). Randomly select h←$ G. From Zp∗ randomly select γ,α1,α2, calculate Ω=gγ,g1=gα1,g2=gα2. Set gT=e(g,g), where g→1=(g1,1,g)∈G3, g→2=(1,g2,g)∈G3 and g→3=(g3,1,g3,2,g3,3)∈g→1∘g→2∈G3, where ξ1,ξ2∈RZn∗; select (u1,u2,w)∈G3, a hash function H:{0,1}∗→{0,1}n, then{cpk,ik,ok}:=n,G,GT,e,h,g,g1,g2,g→1,g→2,g→3,Ω,u1,u2,w,H,γ,(α1,α2).

That is, Setup(1n)→(cpk,ik,ok). Where gpk is the group signature public key, ik and okare the issuer’s and initiator’s keys respectively, and gpk is the group signature public key, ik and ok are the issuer’s and initiator’s keys respectively.

Run (gsk=x,gvk=gx) to generate group M membership certificate K1 and K2. If K1,Ω,K2=e(g,h)e(g,gpk), group signature private key csk:=(gsk,gpk,K1,K2). Message m signature value θ4=g1/(x+H(m)), where x is its private key gsk;ri,si,ti∈Zp∗ where i=1,⋯,4. At the same time, calculate the commitment values c→i=ι(θi)∘g→1ri∘g→2si∘g→3ti and π→1,π→2. Select z1,z2∈RZp∗, using CCApublic key encryption algorithm to encrypt θ1. Each equation has NIZK ϕ, expressed by ϕ→1,ϕ→2, ϕ→3 separately. At the same time, calculate the commitment value d→1,d→2,d→3 of (r¯,s¯,t¯). Finally, the hash value H~ is calculated and the encrypted value v1,v2 is generated. Thus, we can get the group signature value:

σ=(c→1,c→2,c→3,c→4,d→1,d→2,d→3,e1,e2,e3,π→1,π→2,ϕ→1,ϕ→2,ϕ→3,ϑ,v1,v2)(2)

That is GSig(gpk,gsk[i],m)→σ.

Therefore, the integer signature value (σ0,σ1,⋯,σ2u−1) between 0 and 2u−1 can be obtained in the above way and the following bilinear mapping:

T=(T0,T1,⋯,T2u−1)=(e(σ0,g),e(σ1,g),⋯,e(σ2u−1,g))(3)

After receiving the group signature, the verifier returns gvk=GVf(cpk,m,σ). Finally, output the common parameterPP=(p,G,GT,e,g,h,gT,gvk,σ,T).

•   Partylnitial. For example, when the medical data tA of a medical institution needs to be shared with the data of a research institution, the system is triggered. First, we use the key homomorphism technique described in Definition 1 to initialize the patient data information to be shared:

•   Private key: gskA=(xA1,xA2)∈Zp2;

•   Public key: gpkA=(XA1,XA2)∈G2, where XA1=gxA1,XA2=gxA2;

•   Encrypted data: CA=EncgpkA(tA;(y1,y2))=(C1=XA1y1,C2=XA2y2,C3=g1y1+y2⋅htA)

According to the rules of sharing smart contract of medical data security, in the data sharing scenario, we explain how to construct a data sharing sentence x in which medical institutions send t patients’ data to research institutions. Firstly, the certifier obtains the ciphertext of tA, C~=(C~1,C~2,C~3)=(XA1y~1,XA2y~2,gy~1+y~2⋅htA), from the medical CB, and decrypts it to obtain tA. Using randomness y1,y2←$Zp, the prover encrypts the shared data t with its public key and the verifier:

C=(C1,C2,C3)=(XA1y1,XA2y2,gy1+y2⋅ht);C^=(C^1,C^2,C^3=C3)=(XB1y1,XB2y2,gy1+y2⋅ht)(4)

5.2 NIZK Scheme

Assume that P and V are the prover and verifier, respectively. Fiat-Shamir heuristic [26] converts the Σ-protocol into NIZK parameters: After calculating a from P, the challenge c = H(a) is obtained. Among them, H is a random oracle. Finally, calculate z and send the proof (a,c,z) to V.

The proof language L defining the P is as follows:

The data sharing sentence x=(C,C^,gpkA,gpkB,C~)∈L and the corresponding verifier w=(gskA=(xA1,xA2),y1,y2,tA,t), and then

A) Ci=Xiyi,fori=1,2;

B) C^i=XBiyi,fori=1,2;

C) C3=gy1+y2⋅ht;

D) C~3C3=C~11xA1⋅C~21xA2⋅g−y1−y2⋅htA−t;

E) t∈[0,2L),t′=tA−t∈[0,2L),wheret=∑j=0l−1tj⋅(2u)j,t′=∑j=0l−1tj′⋅(2u)j,0≤tj,tj′<2u;orthere exists ω∈Zp,and then

F) h=h1w.

Proof generation by P.

Certifier A takes PP as the public input and generates the NIZK proof of the above statement using private input (gskA,y1,y2,tA,t), as follows:

Proof of formula (A-F) through Σ-protocols. Formula (E) can be proved by the value range in [27,28]. Randomly select samples r1,r2,l,k←$Zp. Calculate i∈{1,2}:Ri=XAiri;R^i=XBiri; For j∈[0,l), randomly select samples vj,vj′,sj,wj,qj,mj←$Zp, and then calculate:Vj=σtjvj,Vj′=σtj′vj′;D1=∏j=0l−1(h(2u)j⋅sj)⋅g1r1+r2;D2=∏j=0l−1(h(2u)j⋅wj)⋅C~1l⋅C~2k⋅g1−r1−r2;aj=Ttj−sj⋅vj⋅gTqj,aj′=Ttj′−wj⋅vj′⋅gTmj; Randomly select c^←$Zp,z^←$Zp, set α=gz^/hc^, and use α to represent (R1,R2,R^1,R^2,{Vj,Vj′}j=0l−1,D1,D2,{aj,aj′}j=0l−1,α). The challenge is obtained through calculation: c~=H(a);c=c~+c^; After that, the secure hash function instance H. Calculation (on modulus p):

z1=r1−c⋅y1;z2=r2−c⋅y2;(5)

zvj=qj−c⋅vj;zvj′=mj−c⋅vj′;(6)

ztj=sj−c⋅sj;ztj′=wj−c⋅tj′;(7)

zl=l−cxA1;zk=k−cxA2;(8)

Finally, A sends proof π=(a,c,z) to B, where z=(z1,z2,{zvj,zvj′}j=0l−1,{ztj,ztj′}j=0l−1,zl,zk,z^).

The verifier V calculates c after receiving the proof π. Using the public input PP,∀i=1,2;j∈[0,l), the verifier checks the following conditions:

Ri=Cic⋅XAizi;(9)

R^i=C^ic⋅XBizi;(10)

D1=∏j=0l−1(h(2u)j⋅ztj)⋅C3c⋅gz1+z2;(11)

D2=∏j=0l−1(h(2u)j⋅ztj′)⋅(C~3C3)c⋅g1z1+z2;(12)

aj=e(Vj,gvk)c⋅e(Vj,g)−ztj′⋅gTzvj′;(13)

aj′=e(Vj′,gvk)c⋅e(Vj′,g)−ztj′⋅gTzvj′;(14)

gz^=α⋅hc^;(15)

5.3 Security of NIZK Scheme

Theorem 1. Assuming DLIN, q-Strong Diffie-Hellman(q-SDH) assumptions, Σ-protocols is a NIZK demonstration with perfect completeness, perfect zero knowledge and computational reliability in oracle model. In addition, complete zero knowledge is established in the standard common random stringmodel.

Proof. The following describes our proof conclusion.

Perfect Completeness. This property can be directly verified.

Soundness. It is assumed that the CCA anonymous dynamic group signature based on q-SDH assumptions is unforgeable, and its reliability is proved under the random oracle model. If the PUSH-PULL traffic(PPT) certifierP∗ is an invalid sentence, generate the acceptance parameter π=(a,c,z), where a=(R1,R2,R^1,R^2,{Vj,Vj′}j=0l−1,D1,D2,{aj,aj′}j=0l−1,α) and z=(z1,z2,{zvj,zvj′}j=0l−1,{ztj,ztj′}j=0l−1,zl,zk,z^).

Then, construct the extractor Ext: P∗ back to return c = H(a). Modify the random oracle so that c' = H(a) and c ≠ c'. Use c' = H(a) to execute P∗. Finally, another valid parameter can appear:

π′=(a,c′,z′=(z1′,z2′,{zvj′,zvj′′}j=0l−1,{ztj′,ztj′′}j=02,zl′,zk′,z^′)).(16)

Verifier information can be extracted by calculation (for i=0,1;j∈[0,l)):

yi=zi−zi′c′−c,tj=ztj−ztj′c′−c,tj′=ztj′−ztj′′c′−c,xA1=c′−czl−zl′,xA2=c′−cZk−zk′.(17)

Under the condition of extracting the prover, if t∉[0,2L) or t′∉[0,2L), you can crack the CCA anonymous dynamic group signature weak selection message attack model with P∗ subroutine.

Perfect zero knowledge. Construct a simulated Sim to prove the proposition h=gw, thereby proving perfect zero-knowledge. See Fig. 3.

Figure 3: Simulator for new NIZK parameters

The parameters are divided into 3 parts:

π=(a=(R1,R2,R^1,R^2,{Vj,Vj′}j=0l−1,D1,D2,{aj,aj′}j=0l−1,α),c,z=(z1,z2,{zvj,zvj′}j=0l−1,{ztj,ztj′}j=0l−1,zl,zk,z^)).(18)

For clarity and convenience, we express the simulation parameters as

π=(a=(R1,R2,R^1,R^2,{Vj,Vj′}j=0l−1,D1,D2,{aj,aj′}j=0l−1,α),c,z=(z1,z2,{zvj,zvj′}j=0l−1,{ztj,ztj′}j=0l−1,zl,zk,z^)).(19)

c^←$Zp is observed to be independent of a, c=H(a)+c^ is uniformly distributed in Zp, and c is also randomly selected from Zp in the simulation. Therefore, the distribution {c} is the same as {c}:{c}≡{c}.

Set f={c}={c}. Under the condition of: {c}≡{c}, c¯∈f is given for each ρ∈Zp because z^,r1,r2,l,k,qj,mj,sj,wj,vj,vj′←$Zp, where j∈[0,l), and for any element z~ in z, we have

Pr[z~=ρ|c=c¯]=1p(20)

In the argument of simulation, under the same conditions, the given value z1,z2,zl,zk,zvj,zvj′,ztj,ztj′,μ←$Zp. For all elements z~ in z, we have

Pr[z~=ρ|c=c¯]=1p.(21)

The Fiat-Shamir heuristic algorithm is applied to the Σ-protocols to build NIZK, so as to achieve perfect zero-knowledge. At the same time, the reliability of the construction is proven in the model.

Set the set of J=z1,z2,{zj3,zj4}j=0l−1,{zj5,zj6}j=0l−1,z7,z8,z9:zi←$Zp,i∈[10]. Given c¯←$f, for each z¯∈J,

Pr[z=z¯|c=c¯]=Pr[z=z¯|c=c¯].(22)

Under the condition of Pr[z=z¯|c=c¯]=Pr[z=z¯|c=c¯], given c¯∈f,z¯∈J, from the verification strategy, message R1,R2,D1,D2,aj,aj′,αinπ is deterministic, where j∈[0,l). For {Vj,Vj′}, we have

Pr[Vj=g|c=c¯,z=z¯]=Pr[σtjvj=g|c=c¯,z=z¯]=1p.(23)

Pr[Vj′=g|c=c¯,z=z¯]=Pr[σtj′vj′=g|c=c¯,z=z¯]=1p.(24)

where g←$G, start from vj, vj′←$Zp.

Set A={a1,a2,{aj3,aj4}j=0l−1,a5,a6,{aj7,aj8}j=0l−1,a9:a1,a2,a3,a4,a5,aj6,aj7,a9←$G,aj7,aj8←$GT}. Therefore, given c¯∈f,z¯∈J, for any a¯∈A,

Pr[a=a¯|c=c¯,z=z¯]=Pr[a=a¯|c=c¯,z=z¯].(25)

Combining (22) and (25), We conclude that for any inconsistent PPT adversary A=(A1,A2),

Pr[(x,w)←A1(1n)(a,c,z)←P(x,w,PP):(x,w)∈RA2(a,c,z)=1]=Pr[(x,w)←A1(1n)(x,c,z)←Sim(x):(x,w)∈RA2(a,c,z)=1](26)

(perfect) get zero knowledge property. The next step is to verify the correctness of NIZK scheme. Instead of verifying

aj=e(Vj,gvk)c⋅e(Vj,g)−ztj′⋅gTzvj′;(27)

aj′=e(Vj′,gvk)c⋅e(Vj′,g)−ztj′⋅gTzvj′;(28)

by calculating 4l pairing calculation. V from Zp, randomly select 2l elements {dj}j=0l−1,{dj′}j=0l−1, and check whether the following formula is valid:

∏j=0l−1ajdj⋅∏j=0l−1(aj′)dj′=e(∏j=0l−1Vjcdj⋅∏j=0l−1(Vj′)cdj′,gvk)⋅e(∏j=0l−1Vj−ztjdj⋅∏j=0l−1(Vj′)−ztj′dj′,g2)⋅gT∑j=0l−1zvjdj+∑j=0l−1zvj′dj′.(29)

In the formula above, only two pairing calculations are calculated, which is more efficient than ((1),(2)). Meanwhile, ((1),(2))⇒ (29): after replacing all values {aj}j=0l−1,{aj′}j=0l−1 in ((1),(2)) , Eq. (29) is obtained.

(29)⇒ ((1),(2)): Consider formula (29):

Right_Side=∏j=0l−1((e(Vj,gvk)c⋅e(Vj,g)−ztj⋅gTzvj)dj⋅(e(Vj′,gvk)c⋅e(Vj′,g)−ztj′⋅gTzvj′)dj′);(30)

LiftSide=∏j=0l−1((aj)dj(aj′)dj′).(31)

If Left_Side=Right_Side, there are two situations:

1) ∀j∈[0,l),aj=e(Vj,gvk)c⋅e(Vj,g)−ztj⋅gTzvj,aj′=e(Vj′,gvk)c⋅e(Vj′,g2)−ztj′⋅gTzvj′. This implies the correctness of equation ((1),(2)).

2) There are some djordj′=0, which can lead to aj≠e(Vj,gvk)c⋅e(Vj,g)−ztj′⋅gTzvj or aj′≠e(Vj′,gvk)c⋅e(VJ′,g)−ztj′⋅gTzvj′for a certain j∈[0,l). This is likely to happen.