2
$\begingroup$

I have been reading about the sigma protocols, specially the OR-Proof.

Many examples just take into account two statements and provide a way to say that one of the statements is valid, but not which one. For example this question zero-knowledge proof of disjunctive statements (OR proofs), or protocol 3 in this article Zero Knowledge Proofs with Sigma Protocols, the section 4 of this work On Σ-protocols and this 2.4 on these slides Σ-protocols.

I would like to extend this to 1 out of $N$ statements (instead of the 1 of out 2 of all the examples I have found). Many work refer Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. I have tried to understand it completely in order to implement a 1 out of $N$ or-protocol but without luck. The secret sharing is introduced, as I understand, to make it $t$ out of $N$, introducing shares, making it slightly more complicated for me.

For the 1 out of 2 protocol, a single challenge is send to the verifier made out of the summation of the "correct" challenge and a "random" challenge. Here is where I guess the extension to more "random" challenges need to take place.

Is it possible to extend the protocol to 1 out of $N$ without using the secret sharing part?

$\endgroup$
1
  • $\begingroup$ I am not familiar with this at all, but is it not possible to regroup $P_1\lor P_2\lor \dots P_k$ as $(P_1\lor \dots P_{\lfloor k/2\rceil})\lor(P_{\lfloor k/2\rceil+1}\lor\dots\lor P_k)$, prove each of the "half-sized proofs", and recurse? $\endgroup$
    – Mark Schultz-Wu
    Sep 23, 2021 at 15:16

1 Answer 1

4
$\begingroup$

If you just want to extend to $1$ out of $N$, a very simple modification of the protocol you are familiar with suffices: a single challenge $e$ is sent to the prover, and the prover can freely choose $N$ values $(e_1, \cdots, e_N)$ such that $\sum_{i=1}^N e_i = e$. Concretely, this means that if the $i$-th statement is the one for which the prover has a witness, they will pick $(e_1, \cdots, e_{i-1}, e_{i+1}, \cdots, e_N)$ uniformly at random in the first step, and when receiving the challenge $e$ from the verifier, they will define $e_i \gets e - \sum_{j\neq i} e_j$.

$\endgroup$
3
  • $\begingroup$ In other words, prove one true statement and simulate all others. Start by choosing $N-1$ challenges at random for simulation, and later calculate the proper challenge for proving. $\endgroup$ Sep 24, 2021 at 20:49
  • $\begingroup$ Nice, that sound easy to do. I plan to apply Fiat Shamir heuristic to make it non interactive, will work it out and post it here. I was wondering, with this 1-out-of-N protocol, is it guaranteed that one of the statements is correct? Or could a prover make all the statements false and claim "1 out of N" is correct? $\endgroup$
    – wattlab
    Sep 26, 2021 at 15:24
  • $\begingroup$ It is guaranteed that at least one of the statements is correct, and that the prover knows the witness for at least one of the correct statements. It is not possible to falsely claim that at least one ouf of the N statements is correct. $\endgroup$ Sep 27, 2021 at 21:26

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.