zkMe Docs
GithubDiscord
Ask or search…
⌃K
Links
Comment on page

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.
Me - Profiling Suite - Previous
Integration Guide
Next
zkMe ZKP
Last modified 2mo ago