Extending the OR-proof to more than two statements

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?

• 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? Commented Sep 23, 2021 at 15:16

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$$.
• 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. Commented Sep 24, 2021 at 20:49