Score:2

Extending the OR-proof to more than two statements

cn flag

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?

Mark avatar
ng flag
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?
Score:2
cn flag

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

Vadym Fedyukovych avatar
in flag
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.
cn flag
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?
Geoffroy Couteau avatar
cn flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.