0
$\begingroup$

Given the following Zero-knowledge set-membership protocol https://infoscience.epfl.ch/record/128718/files/CCS08.pdf]. That is given in the following steps (Please refer to page 9).

  1. The Verifier

-select a set of elements denoted as $\phi$

-Select $x \in_{R} \mathbb{Z}_{p}$ and computes $y \leftarrow g^{x}$ and $A_{i} \leftarrow g^{\frac{1}{x+i}}$ for every $i \in \Phi$

  1. The Prover

-select an element in the set $\phi$ denoted as $\sigma$

-Select $v \in_{R} \mathbb{Z}_{p}$ and computes $V \leftarrow A_{\sigma}^{v}$

-Select $s, t, m \in_{R} \mathbb{Z}_{p}$ and computes $a \leftarrow e(V, g)^{-s} e(g, g)^{t}$ and $D \leftarrow g^{s} h^{m}$

-computes challenge c using fiat-shamir heuristic as: $c=H(V\|a\| D)$

-computes $z_{\sigma} \leftarrow s-\sigma c, z_{v} \leftarrow t-v c,$ and $z_{r} \leftarrow m-r c$

-sends $C, c, a, D, Z_{\sigma}, Z_{v}, Z_{r}$ to the verifier

  1. The verifier validates the proof by checking:

$D \stackrel{?}{=} C^{c} h^{z_{r}} g^{z_{\sigma}}$ and $a \stackrel{?}{=} e(V, y)^{c} \cdot e(V, g)^{-z_{\sigma}} \cdot e(g, g)^{z_{v}}$

Following, the following Theorem 1 (that proofs the zero-knowledge of the above protocol) as follows:

"the extraction property implies that for any prover P* that convinces V with probability ε, there exists an extractor which interacts with P* and outputs a witness (σ, r, v) with probability poly(ε). Moreover, if we assume that the extractor input consists of two transcripts, i.e.

$$ \left\{y,\left\{A_{i}\right\}, V, a, D, c, c^{\prime}, z_{\sigma}, z_{\sigma}^{\prime}, z_{v}, z_{v}^{\prime}, z_{r}, z_{r}^{\prime}\right\} $$

the witness can be obtained by computing: $$ \sigma=\frac{z_{\sigma}-z_{\sigma}^{\prime}}{c^{\prime}-c} ; \quad r=\frac{z_{r}-z_{r}^{\prime}}{c^{\prime}-c} ; \quad v=\frac{z_{v}-z_{v}^{\prime}}{c^{\prime}-c} $$

The extractor succeeds when $\left(c^{\prime}-c\right) \text { is invertible in } \mathbb{Z}_{p}$"

My question:

Considering the ZKSM and proof given in the paper, if we consider the case where the following data

$${y,{A_i },V,a,D,c,Z_σ,Z_v,Z_r}$$ is made public (e.g., stored in public blockchain that acts the verifier). Thus, an adversary succeeds in getting the witness ($\sigma$, r, v) if he is able to obtain $c^{'}$ such that $\left(c^{\prime}-c\right)$ is invertible in $Z_p$. Is this case doable?. In other words, considering properties of fields
can the adversary find $c^{'}$ such that $\left(c^{\prime}-c\right)$ is invertible in $Z_p$?.

$\endgroup$
1
$\begingroup$

Reading the last sentence:

Can an adversary find a $c’$ such that $c’ - c= 0$ in a field. This follows from the definition of a field, whenever $c’ != c$

$\endgroup$
  • $\begingroup$ The paper stated that the protocol is efficient and secure. I am really not able to understand that $\endgroup$ – Heba Mohsen Jun 4 at 23:28
  • $\begingroup$ My guess is that they are saying that the system is compromised when you can find a c prime that is different from c. In terms of schemes, this could mean that if you can find two different inputs that lead to the same output. You will need to read up on where c prime and c is being used. Checking if two different c values leading to the same output is bad? $\endgroup$ – user679128 Jun 5 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.