Security Model

The robust security framework that underlies zkMe.

Notations

zk-SNARK

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

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

$\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) \in R_C$ and $R_C$ is a relation defined by $C$.

$\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 $C$. i.e:

$$\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 $C$ is short, unrelated to the complexity of $C$. In addition, the $\mathsf{Verify}$ algorithm is a deterministic polynomial time algorithm, also unrelated to the complexity of $C$.

• Computational Zero Knowledge: A valid proof $\pi$ is computationally zero knowledge if it does not leak any information about the witness to PPT adversary $\mathcal{A}$. More formally, for any PPT $\mathcal{A}$, a simulated algorithm $\widehat{\mathsf{Setup}}$ can produce a common reference string $\mathsf{crs}$ and a trapdoor $\tau$,which is used in $\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. $\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 $\mathcal{A}$ even after $\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 $\mathcal{A}$, there exist simulator algorithms $\widehat{\mathsf{Setup}}$ and $\widehat{\mathsf{Prove}}$ a probabilistic polynomial-time witness extractor $\mathcal{X}$, such that the following probability is negligible:

$$\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 $\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 $\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:

• $\mathcal{F}.setup(\cdot)$

Initialize the public parameters $pp$

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

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

• $\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 $sk_1, tesk_1$. Zkme selects random $sk_2, tesk_2$.

Two parties runs $\mathsf{ComputeGlobalPubKey}(sk_1, sk_2) \rightarrow pk_{SSI}$

User runs $\mathsf{ComputePubKey}(sk_1) \rightarrow pk_{E}$

Two parties runs $\mathsf{ComputeGlobalPubKey}(tesk_1, tesk_2) \rightarrow pk_{TE}$

Publish $(pk_{SSI},pk_{E},pk_{TE})$

• $\mathcal{F}.mintSSISBT(\cdot)$

Client scans the document into IDdata

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

runs

$\mathsf{ThresholdEncrypt}(pk_{TE},IDdata) \rightarrow enc_{id}$

$\mathsf{Encrypt}(pk_{E},tesk_{1}) \rightarrow enc_{t1}$

$\mathsf{ProveAll}(IDdata,\mathcal{C},pk) \rightarrow \lbrace \pi_i \rbrace_{i \in [\mathcal{C}]}$

Sends $(\mathcal{C},\lbrace \pi_i \rbrace_{i \in [\mathcal{C}]},enc_{id},enc_{t1})$ to server

• $\mathcal{F}.transferSBT(\cdot)$

Client downloads $enc_{t1}$ from $SBT_{ssi}$, and runs

$\mathsf{Decrypt}(sk_{1},enc_{t1}) \rightarrow tesk_{1}$

$\mathsf{ComputeCapsule}(sk_{assert},tesk_{1}) \rightarrow capsule$

Sends $capsule$ to server

Server calls $\mathsf{mint}(enc_{\mathcal{C}}, enc_{\pi},capsule)\rightarrow SBT_{assert}$

• $\mathcal{F}.showSBT(\cdot)$

Client downloads $capsule$ from $SBT_{asset}$, and runs

$\mathsf{ComputeRK}(sk_{asset},pk_{project}) \rightarrow rk$

Sends $rk$ to server. Server calls $\mathsf{ReEncrypt}(SBT_{asset},rk, targetProject) \rightarrow rk$

• $\mathcal{F}.verifyShow(\cdot)$

DApp watches the event and gets $rk$ , and runs

$\mathsf{PDecrypt}(sk_{project}, rk) \rightarrow tesk_1$

$\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 $\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 $\mathcal{F}.mintSSISBT(\cdot)$. Let $\mathcal{Real}$ be a random variable representing the joint view of zkme server and nodes in blockchain. If there exists a PPT simulator $\mathcal{Sim}$ such that the output of $\mathcal{Sim}$ is computationally indistinguishable from the output of $\mathcal{Real}$.

Hybrid_0: Hybrid_0 is a real view where PPT adversary $\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 $\mathsf{ThresholdEncrypt}(pk_{TE},r) \rightarrow \mathbb{P}$ where $r$ is uniformly random. Since only the content of $enc_{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 $\mathsf{ProveAll}(IDdata',\mathcal{B},pk) \rightarrow \lbrace \pi_i' \rbrace_{i \in [\mathcal{B}]}$ where $\mathcal{B}$ has the same amount of questions as $\mathcal{C}$ and the distribution of $\mathcal{B}$ is uniformly random and every $\pi_i'$ is correctly generated against the question in $\mathcal{B}$. Since only the content of $\mathcal{C}$ and $\lbrace \pi_i \rbrace_{i \in [\mathcal{C}]}$ is changed, the zk-SNARK satisfies Completeness and Computational Zero Knowledge, all $\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 $\mathsf{ThresholdEncryptAll}(pk_{TE},\lbrace ques_i \rbrace_{i \in [\mathcal{B}]}) \rightarrow enc_{\mathcal{B}}$. Since only the content of $\mathcal{C}$ and $enc_{\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 $\mathsf{ThresholdEncryptAll}(pk_{TE}, \lbrace \pi_i' \rbrace_{i \in [\mathcal{B}]}) \rightarrow enc_{\pi}'$, where $\lbrace \pi_i' \rbrace_{i \in [\mathcal{B}]}$ are independent with $\lbrace \pi_i \rbrace_{i \in [\mathcal{C}]}$. Since only the content of $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 $\mathcal{Sim}$ sampled from the distribution described above so that its output is computationally indistinguishable from the output of $\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 $\mathcal{A}$ succeeds in breaking unforgeability becomes negligible.

Hybrid_0: Hybrid_0 is a real view where PPT adversary $\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 $\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 $\mathcal{A}$ constructs the ciphertext and proof $(enc_{\mathcal{C}'}, enc_{\pi'})$ based on fake question set and modifies the data in SSI blockchain. Since the public blockchain is immutable. $\mathcal{A}$ cannot change the verified ciphertext data $(enc_{\mathcal{C}}, enc_{\pi})$ of $SBT_{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'$ based on $sk_{\mathcal{A}}$ and tries to transfer his/her SBT to asset wallet $\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 $\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 $\mathcal{A}$ succeeds in breaking traceability becomes negligible.

Hybrid_0: Hybrid_0 is a real view where PPT adversary $\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 $\mathcal{A}$ constructs the fake ciphertext $enc_{id'}$ where plaintext is fake identity data $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 $\mathcal{A}$ generates the ciphertext $enc_{id'}$ and tries to replace the data $enc_{id}$ in IPFS. Since the decentralized storage is immutable. $\mathcal{A}$ cannot change the data $enc_{id}$ in IPFS. Hybrid_2 is indistinguishable from Hybrid_1.

Hybrid_3: Hybrid_3 is identical to Hybrid_2, except that $\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.