Group proofs

[dbosk]

Can we group the proofs?

When the prover sends his pid to the witness, several witnesses will hear that (it's a broadcast channel). Can the witnesses all provide a challenge each, which the prover uses to convince all the witnesses with just one computation?

One possibility is that all the challenges c_1, ..., c_n are used to produce the challenge c = H(c_1, ..., c_n). The use of H makes it impossible for the prover to cheat (Fiat-Shamir heuristic) and the required input of c_1, ..., c_n makes it interactive.

[dbosk]

Well, those c_1, ..., c_n must be sent at the same time, and the c must be computed during the fast phase.

[dbosk]

Actually, the c_1, ..., c_n and c can be computed before. We just do several of them and then one witness chooses which one to be used. The other witnesses must be able to observe this exchange.

This might be difficult though. And the other witnesses can't know if the one who chooses the challenge colludes with the prover.