# Is the following non-interactive zero-knowledge set membership protocol provable 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$$