Witness-indistinguishable (WI) proofs are fundamental for the design of cryptographic protocols, particularly when they are also proofs of knowledge (PoK). In a WIPoK the prover \(\mathcal {P}\) proves knowledge of a witness certifying the veracity of a statement \(x \in L\) to a verifier \(\mathcal {V}\) . WIPoKs can be used directly in some applications (e.g., in identification schemes) or can be a building block for stronger security notions (e.g., for zero-knowledge proofs using the FLS [76] paradigm or for round-optimal secure computation [124]). Often in cryptographic protocols, there is a preamble phase that has the purpose of establishing, at least in part, a statement to be proven with a WI proof. In such cases, since one of the statements is fully specified only when the preamble is completed, the WI proof can start only after the preamble ends. Hence, the overall round complexity of protocols that follow this paradigm amounts to the sum of the round complexity of the preamble and of the WI proof. In [133] (See [162] for a detailed description of [133].), Lapidot and Shamir (and later on Feige et al. in [76]) show a three-round proof of knowledge for Hamiltonian graphs which has the special property that enjoys the delayed-input property. In more detail, the prover can compute the first round of the proof, without knowing the theorem to be proved (that is, the graph) but only needs to know its size (that is, the number of vertices). In this chapter, we show how to design efficient proof systems that enjoy a mild form of delayed input. In particular, the focus of the chapter is on the design of proof systems for OR relations. In this the prover wants to prove that either \(x_0\in L\) or \(x_1\in L\) . We show a three-round protocol that allows the prover to prove such a statement without the need to know both instances when generating the first message of the proof. Our protocol is presented in the form of a compiler that works over a big class of special three-round proof of knowledge known as Sigma-Protocols.

Improved OR Composition

章节
发表日期：

2026年

查看全文

Michele Ciampi,
Luisa Siniscalchi

摘要

Witness-indistinguishable (WI) proofs are fundamental for the design of cryptographic protocols, particularly when they are also proofs of knowledge (PoK). In a WIPoK the prover \(\mathcal {P}\) proves knowledge of a witness certifying the veracity of a statement \(x \in L\) to a verifier \(\mathcal {V}\) . WIPoKs can be used directly in some applications (e.g., in identification schemes) or can be a building block for stronger security notions (e.g., for zero-knowledge proofs using the FLS [76] paradigm or for round-optimal secure computation [124]). Often in cryptographic protocols, there is a preamble phase that has the purpose of establishing, at least in part, a statement to be proven with a WI proof. In such cases, since one of the statements is fully specified only when the preamble is completed, the WI proof can start only after the preamble ends. Hence, the overall round complexity of protocols that follow this paradigm amounts to the sum of the round complexity of the preamble and of the WI proof. In [133] (See [162] for a detailed description of [133].), Lapidot and Shamir (and later on Feige et al. in [76]) show a three-round proof of knowledge for Hamiltonian graphs which has the special property that enjoys the delayed-input property. In more detail, the prover can compute the first round of the proof, without knowing the theorem to be proved (that is, the graph) but only needs to know its size (that is, the number of vertices). In this chapter, we show how to design efficient proof systems that enjoy a mild form of delayed input. In particular, the focus of the chapter is on the design of proof systems for OR relations. In this the prover wants to prove that either \(x_0\in L\) or \(x_1\in L\) . We show a three-round protocol that allows the prover to prove such a statement without the need to know both instances when generating the first message of the proof. Our protocol is presented in the form of a compiler that works over a big class of special three-round proof of knowledge known as Sigma-Protocols.