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


2 Answers 2


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$

  • $\begingroup$ The paper stated that the protocol is efficient and secure. I am really not able to understand that $\endgroup$ Commented Jun 4, 2019 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$
    – user69644
    Commented Jun 5, 2019 at 0:18

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.

This power-to-rewind of extractor algorithm looks tricky. It could be hard to understand from a practical point of view. Hopefully one could understand it as a formalization of another tricky idea: what exactly "knowledge" means.

For a practical approach: make sure to always pick fresh random numbers at step one, never reuse (rewind).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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