Security Model

The robust security framework that underlies zkMe.

Notations

zk-SNARK

Let R=(c,x)R={(c,x)} be a polynomial relation of statements cc and witness xx. A zk-SNARK Ī \Pi for RR is composed of the following 3 polynomial time algorithms: Setup,Prove,Verify\mathsf{Setup,Prove,Verify} and works as follows. It satisfies completeness, succinctness, computational zero knowledge and simulation extractability.

Setup(1Ī»,C)ā†’crs\mathsf{Setup}(1^\lambda, C)\rightarrow \mathsf{crs} : It takes the security parameter Ī»\lambda and a circuit CC as input, and generates a common reference string crs\mathsf{crs} .

Prove(crs,c,x)ā†’Ļ€\mathsf{Prove}({\mathsf{crs},c,x)}\rightarrow \pi : It takes a public input (statement) c and a private input (witness) x and generates and returns proof Ļ€\pi, where (c,x)āˆˆRC(c,x) \in R_C and RCR_C is a relation defined by CC.

Verify(crs,c,Ļ€)ā†’{0/1}\mathsf{Verify}({\mathsf{crs},c,\pi)} \rightarrow \lbrace 0/1 \rbrace : This algorithm verifies proof Ļ€\pi with regard to public input c. It returns 1 if the proof is verified successfully and 0 otherwise.

  • Completeness: An honest prover with a valid witness can always convince an honest Verifier for a given security parameter Ī»\lambda and arithmetic circuit CC. i.e:

Prā”[Verifyā”(crs,Ļ€,c)=1crsā†Setup(1Ī»,C)Ļ€ā†Prove(crs,c,x)]=1\operatorname{Pr}\left[\begin{array}{l|l} \operatorname{\mathsf{Verify}}(\mathsf{crs}, \pi, c)=1 & \begin{array}{l} \mathsf{crs} \leftarrow \mathsf{Setup}\left(1^{\lambda}, C\right) \\ \pi \leftarrow \mathsf{Prove}(\mathsf{crs}, c, x) \end{array} \end{array}\right]=1
  • Succinctness: The size of a zk-SNARK proof Ļ€\pi about CC is short, unrelated to the complexity of CC. In addition, the Verify\mathsf{Verify} algorithm is a deterministic polynomial time algorithm, also unrelated to the complexity of CC.

  • Computational Zero Knowledge: A valid proof Ļ€\pi is computationally zero knowledge if it does not leak any information about the witness to PPT adversary A\mathcal{A}. More formally, for any PPT A\mathcal{A}, a simulated algorithm Setup^\widehat{\mathsf{Setup}} can produce a common reference string crs\mathsf{crs} and a trapdoor Ļ„\tau,which is used in Prove^\widehat{\mathsf{Prove}} to produce a simulated proof Ļ€^\hat{\pi}. This simulated proof Ļ€^\hat{\pi} is indistinguishable from a honestly generated proof. Computational Zero Knowledge means the honestly generated proof is zero-knowledge since the simulated proof does not contain any information about the witness. Prā”[A(crs,Ļ€,c)=1crsā†Setup(1Ī»,C)Ā Ļ€ā†Prove(crs,c,x)]ā‰ƒPrā”[A(crs^,Ļ€^,c)=1(crs^,Ļ„)ā†Setup^(1Ī»,C)Ā Ļ€^ā†Prove^(crs^,Ļ„,c)]\operatorname{Pr}\left[\begin{array}{l|l} \mathcal{A}(\mathsf{crs}, \pi, c)=1 & \begin{array}{l} \mathsf{crs} \leftarrow \mathsf{Setup}\left(1^{\lambda}, C\right) \ \pi \leftarrow \mathsf{Prove}(\mathsf{crs}, c, x) \end{array} \end{array}\right] \simeq \operatorname{Pr}\left[\begin{array}{l|l} \mathcal{A}(\widehat{\mathsf{crs}}, \hat{\pi}, c)=1 & \begin{array}{l} (\widehat{\mathsf{crs}}, \tau) \leftarrow \widehat{\mathsf{Setup}}\left(1^{\lambda}, C\right) \ \hat{\pi} \leftarrow \widehat{\mathsf{Prove}}(\widehat{\mathsf{crs}}, \tau, c) \end{array} \end{array}\right]

  • Simulation Extractability: The simulator can extract a witness from a proof generated by PPT adversary A\mathcal{A} even after A\mathcal{A} is allowed to use the simulation oracle and has seen many simulated proofs, which imply knowledge soundness. This property ensures that the prover knows a valid witness if he can produce a valid proof. For every PPT adversary A\mathcal{A}, there exist simulator algorithms Setup^\widehat{\mathsf{Setup}} and Prove^\widehat{\mathsf{Prove}} a probabilistic polynomial-time witness extractor X\mathcal{X}, such that the following probability is negligible:

Prā”[(c,x)āˆ‰RC(crs^,Ļ„)ā†Setup^(1Ī»,C)(c,Ļ€)āˆ‰Q(c,Ļ€)ā†AProve^(crs^,Ļ„,ā‹…)(crs^)Verify(crs^,Ļ€,c)=1xā†X(transA)]\operatorname{Pr}\left[\begin{array}{l|l} (c, x) \notin \mathcal{R}_{C} & (\widehat{\mathsf{crs}}, \tau) \leftarrow \widehat{\mathsf{Setup}}\left(1^{\lambda}, C\right) \\ (c, \pi) \notin \mathcal{Q} & (c, \pi) \leftarrow \mathcal{A}^{\widehat{\mathsf{Prove}}}(\widehat{\mathsf{crs}}, \tau, \cdot)(\widehat{\mathsf{crs}}) \\ \mathsf{Verify}(\widehat{\mathsf{crs}}, \pi, c)=1 & x \leftarrow \mathcal{X}\left(\mathsf{trans}_{\mathcal{A}}\right) \end{array}\right]

2-party ECDSA

The signing private key is split into key shares: one for the Issuer, one for the Holder, and one for the Regulator (where applicable). Only the three of them working together can sign the message. The signature on the 2-ECDSA cannot be forged by any PPT adversary A\mathcal{A}. The decryption private key is split into two key shares, one for the zk-SNARK and one for the Holder.

The ideal functionality F\mathcal{F} for zkMe

We design the zkMe network by combining all the preliminaries (see sequence diagram above) and describe the ideal functionality as follows:

  • F.setup(ā‹…)\mathcal{F}.setup(\cdot)

Initialize the public parameters pppp

Decide on kyc template T:=(Q,c,addkyc)\mathcal{T}:=(\mathcal{Q}, c, add_{kyc})

Publish (pp,T)(pp,\mathcal{T})

  • F.registry(pp,sk1,sk2,tesk1,tesk2)ā†’(pkE,pkSSI,AddSSI,pkTE)\mathcal{F}.registry(pp, sk_1, sk_2, tesk_1, tesk_2) \rightarrow (pk_{E},pk_{SSI},Add_{SSI},pk_{TE})

Generate key shares

User selects random sk1,tesk1sk_1, tesk_1. Zkme selects random sk2,tesk2sk_2, tesk_2.

Two parties runs ComputeGlobalPubKey(sk1,sk2)ā†’pkSSI\mathsf{ComputeGlobalPubKey}(sk_1, sk_2) \rightarrow pk_{SSI}

User runs ComputePubKey(sk1)ā†’pkE\mathsf{ComputePubKey}(sk_1) \rightarrow pk_{E}

Two parties runs ComputeGlobalPubKey(tesk1,tesk2)ā†’pkTE\mathsf{ComputeGlobalPubKey}(tesk_1, tesk_2) \rightarrow pk_{TE}

Publish (pkSSI,pkE,pkTE)(pk_{SSI},pk_{E},pk_{TE})

  • F.mintSSISBT(ā‹…)\mathcal{F}.mintSSISBT(\cdot)

Client scans the document into IDdata

queries the kyc question set C\mathcal{C} and proving keys

runs

ThresholdEncrypt(pkTE,IDdata)ā†’encid \mathsf{ThresholdEncrypt}(pk_{TE},IDdata) \rightarrow enc_{id}

Encrypt(pkE,tesk1)ā†’enct1 \mathsf{Encrypt}(pk_{E},tesk_{1}) \rightarrow enc_{t1}

ProveAll(IDdata,C,pk)ā†’{Ļ€i}iāˆˆ[C]\mathsf{ProveAll}(IDdata,\mathcal{C},pk) \rightarrow \lbrace \pi_i \rbrace_{i \in [\mathcal{C}]}

Sends (C,{Ļ€i}iāˆˆ[C],encid,enct1)(\mathcal{C},\lbrace \pi_i \rbrace_{i \in [\mathcal{C}]},enc_{id},enc_{t1}) to server

  • F.transferSBT(ā‹…)\mathcal{F}.transferSBT(\cdot)

Client downloads enct1enc_{t1} from SBTssiSBT_{ssi}, and runs

Decrypt(sk1,enct1)ā†’tesk1 \mathsf{Decrypt}(sk_{1},enc_{t1}) \rightarrow tesk_{1}

ComputeCapsule(skassert,tesk1)ā†’capsule \mathsf{ComputeCapsule}(sk_{assert},tesk_{1}) \rightarrow capsule

Sends capsulecapsule to server

Server calls mint(encC,encĻ€,capsule)ā†’SBTassert\mathsf{mint}(enc_{\mathcal{C}}, enc_{\pi},capsule)\rightarrow SBT_{assert}

  • F.showSBT(ā‹…)\mathcal{F}.showSBT(\cdot)

Client downloads capsulecapsule from SBTassetSBT_{asset}, and runs

ComputeRK(skasset,pkproject)ā†’rk \mathsf{ComputeRK}(sk_{asset},pk_{project}) \rightarrow rk

Sends rkrk to server. Server calls ReEncrypt(SBTasset,rk,targetProject)ā†’rk \mathsf{ReEncrypt}(SBT_{asset},rk, targetProject) \rightarrow rk

  • F.verifyShow(ā‹…)\mathcal{F}.verifyShow(\cdot)

DApp watches the event and gets rkrk , and runs

PDecrypt(skproject,rk)ā†’tesk1 \mathsf{PDecrypt}(sk_{project}, rk) \rightarrow tesk_1

ThresholdDecrypt(tesk1,encC,encĻ€)ā†’({quesi}iāˆˆ[C],{Ļ€i}iāˆˆ[C]) \mathsf{ThresholdDecrypt}(tesk_1,enc_{\mathcal{C}}, enc_{\pi}) \rightarrow (\lbrace ques_i \rbrace_{i \in [\mathcal{C}]}, \lbrace \pi_i \rbrace_{i \in [\mathcal{C}]})

If VerifyAll(C,{Ļ€i}iāˆˆ[C])==1\mathsf{VerifyAll}(\mathcal{C},\lbrace \pi_i \rbrace_{i \in [\mathcal{C}]}) == 1, authorization checking

Security Proof

Theorem 1:

If the zk-SNARK scheme Ī \Pi satisfies Completeness and Computational Zero Knowledge, the 2-party threshold encryption scheme is secure against chosen-plaintext attacks, then the proposed zk-SNARK provides zk-SNARK.

Proof of Theorem 1:

We adopt the standard hybrid argument to prove Theorem 1 by showing that our zkMe network securely realizes the ideal functionality F.mintSSISBT(ā‹…)\mathcal{F}.mintSSISBT(\cdot) . Let Real\mathcal{Real} be a random variable representing the joint view of zkme server and nodes in blockchain. If there exists a PPT simulator Sim\mathcal{Sim} such that the output of Sim\mathcal{Sim} is computationally indistinguishable from the output of Real\mathcal{Real}.

Hybrid_0: Hybrid_0 is a real view where PPT adversary A\mathcal{A} tries to find the identity information of wid.

Hybrid_1: Hybrid_1 is identical to Hybrid_0, except that the simulated wid runs ThresholdEncrypt(pkTE,r)ā†’P \mathsf{ThresholdEncrypt}(pk_{TE},r) \rightarrow \mathbb{P} where r r is uniformly random. Since only the content of encidenc_{id} is changed, the ThresholdEncrypt function is secure against chose-plaintext attacks, Hybrid_1 is indistinguishable from Hybrid_0.

Hybrid_2: Hybrid_2 is identical to Hybrid_1, except that the simulated wid runs ProveAll(IDdataā€²,B,pk)ā†’{Ļ€iā€²}iāˆˆ[B]\mathsf{ProveAll}(IDdata',\mathcal{B},pk) \rightarrow \lbrace \pi_i' \rbrace_{i \in [\mathcal{B}]} where B\mathcal{B} has the same amount of questions as C\mathcal{C} and the distribution of B\mathcal{B} is uniformly random and every Ļ€iā€²\pi_i' is correctly generated against the question in B\mathcal{B}. Since only the content of C\mathcal{C} and {Ļ€i}iāˆˆ[C]\lbrace \pi_i \rbrace_{i \in [\mathcal{C}]} is changed, the zk-SNARK satisfies Completeness and Computational Zero Knowledge, all {Ļ€iā€²}iāˆˆ[B]\lbrace \pi_i' \rbrace_{i \in [\mathcal{B}]} are verified valid, Hybrid_2 is indistinguishable from Hybrid_1.

Hybrid_3: Hybrid_3 is identical to Hybrid_2, except that the simulated zkme server runs ThresholdEncryptAll(pkTE,{quesi}iāˆˆ[B])ā†’encB \mathsf{ThresholdEncryptAll}(pk_{TE},\lbrace ques_i \rbrace_{i \in [\mathcal{B}]}) \rightarrow enc_{\mathcal{B}}. Since only the content of C\mathcal{C} and encCenc_{\mathcal{C}} is changed, the ThresholdEncrypt function is secure against chose-plaintext attacks, Hybrid_3 is indistinguishable from Hybrid_2.

Hybrid_4: Hybrid_3 is identical to Hybrid_3, except that the simulated zkme server runs ThresholdEncryptAll(pkTE,{Ļ€iā€²}iāˆˆ[B])ā†’encĻ€ā€² \mathsf{ThresholdEncryptAll}(pk_{TE}, \lbrace \pi_i' \rbrace_{i \in [\mathcal{B}]}) \rightarrow enc_{\pi}', where {Ļ€iā€²}iāˆˆ[B]\lbrace \pi_i' \rbrace_{i \in [\mathcal{B}]} are independent with {Ļ€i}iāˆˆ[C]\lbrace \pi_i \rbrace_{i \in [\mathcal{C}]}. Since only the content of encĻ€enc_{\mathcal{\pi}} is changed, the ThresholdEncrypt function is secure against chose-plaintext attacks, Hybrid_4 is indistinguishable from Hybrid_3.

The argument proves that there is a simulator Sim\mathcal{Sim} sampled from the distribution described above so that its output is computationally indistinguishable from the output of Real\mathcal{Real}. Hence, our scheme can provide anonymity.

Theorem 2:

If the zkMe client provides a trusted execution environment, the public blockchain is immutable, the commitment scheme is binding, then the proposed zk-SNARK provides unforgeability.

Proof of Theorem 2:

We also adopt the standard hybrid argument to prove Theorem 2, where the probability that PPT adversary A\mathcal{A} succeeds in breaking unforgeability becomes negligible.

Hybrid_0: Hybrid_0 is a real view where PPT adversary A\mathcal{A} tries to mint SBT with fake document and transfer others' SBT_ssi to his/her asset wallet.

Hybrid_1: Hybrid_1 is identical to Hybrid_0, except that A\mathcal{A} constructs the fake document and shows it to zkme client. Since the zkme client provides a trusted execution environment, any forged document can not pass validation. Hybrid_1 is indistinguishable from Hybrid_0.

Hybrid_2: Hybrid_2 is identical to Hybrid_1, except that A\mathcal{A} constructs the ciphertext and proof (encCā€²,encĻ€ā€²)(enc_{\mathcal{C}'}, enc_{\pi'}) based on fake question set and modifies the data in SSI blockchain. Since the public blockchain is immutable. A\mathcal{A} cannot change the verified ciphertext data (encC,encĻ€)(enc_{\mathcal{C}}, enc_{\pi}) of SBTssiSBT_{ssi} in SSI blockchain. Hybrid_2 is indistinguishable from Hybrid_1.

Hybrid_3: Hybrid_3 is identical to Hybrid_2, except that colluder constructs the capsuleā€²capsule' based on skAsk_{\mathcal{A}} and tries to transfer his/her SBT to asset wallet A\mathcal{A}. Since the commitment scheme is binding. It can be detected by mint server if the private key of asset wallet is not bound to public key of SSI wallet. The asset wallet of A\mathcal{A} can not receive the SBT from other ones. Hybrid_3 is indistinguishable from Hybrid_2. Hence, under these assumptions of Theorem 2, the proposed system provides the unforgeability property.

Theorem 3:

If the zkMe client provides a trusted execution environment, the (k, n)-threshold SSS is correct, the decentralized storage is immutable, then the designed zkMe network provides traceability.

Proof of Theorem 3

We also adopt the standard hybrid argument to prove Theorem 3, where the probability that PPT adversary A\mathcal{A} succeeds in breaking traceability becomes negligible.

Hybrid_0: Hybrid_0 is a real view where PPT adversary A\mathcal{A} tries to stop the regulator committee to trace back the real IDdata.

Hybrid_1: Hybrid_1 is identical to Hybrid_0, except that A\mathcal{A} constructs the fake ciphertext encidā€² enc_{id'} where plaintext is fake identity data IDdataā€²IDdata'. Since the zkme client provides a trusted execution environment, any forged document can not pass validation. Hybrid_1 is indistinguishable from Hybrid_0.

Hybrid_2: Hybrid_2 is identical to Hybrid_1, except that A\mathcal{A} generates the ciphertext encidā€²enc_{id'} and tries to replace the data encidenc_{id} in IPFS. Since the decentralized storage is immutable. A\mathcal{A} cannot change the data encidenc_{id} in IPFS. Hybrid_2 is indistinguishable from Hybrid_1.

Hybrid_3: Hybrid_3 is identical to Hybrid_2, except that A\mathcal{A} tries to break the correctness property of the (k, n)-threshold SSS.. Since the (k, n)-threshold SSS is correct. Hybrid_3 is indistinguishable from Hybrid_2.

Hence, under these assumptions of Theorem 3, the proposed system provides the traceability property.

Last updated