# Is the following non-interactive zero-knowledge set membership protocol provably secure?

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$$?.

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$$
This second challenge $$c'$$ and second part of the transcript is coming from extractor algorithm, a part of proof of knowledge definition. Extractor algorithm is formally given a power to rewind the prover to the state his first message was sent, so it could pick another challenge. Witness produced by extractor in expected polynomial time is the major requirement from proof of knowledge definition.