Yu Xia

In STOC 2019 Canetti et al. showed how to soundly instantiate the Fiat-Shamir transform assuming that prover and verifier have access to the key of a correlation intractable hash function for efficiently searchable relations. The transform requires the starting protocol to be a special 3-round public-coin scheme that Canetti et al. call trapdoor sigma-protocol. One downside of the Canetti et al. approach is that the key of the hash function can be used only once (or a pre-determined bounded number of times). That is, each new zero-knowledge proof requires a freshly generated hash key (i.e., a freshly generated setup). This is in contrast to what happens with the standard Fiat-Shamir transform, where the prover, having access to the same hash function(modelled as a random-oracle), can generate an unbounded number of proofs that are guaranteed to be zero-knowledge and sound.

As our main contribution we extend the results of Canetti et al., by proposing a multi-theorem protocol that follows the Fiat-Shamir paradigm and relies on correlation intractable hash functions. Moreover, our protocol remains zero-knowledge and sound even against adversaries that choose the statement to be proven (and the witness for the case of zero-knowledge) adaptively on the key of the hash function. Our construction is presented in the form of a compiler, that follows the Fiat-Shamir paradigm, which takes as input any trapdoor sigma-protocol for the NP-language L and turns it into a non-interactive zero-knowledge protocol that satisfies the properties we mentioned. To be best of our knowledge, ours is the first compiler that follows the Fiat-Shamir paradigm to obtain a multi-theorem adaptive NIZK relying on correlation intractable hash functions.

The prior works of Cohen, Garay and Zikas (Eurocrypt 2020), Damgård, Magri, Ravi, Siniscalchi and Yakoubov (Crypto 2021) and Damgård, Ravi, Siniscalchi and Yakoubov (Eurocrypt 2023) study 2-round Multi-Party Computation (where some form of set-up is required). Motivated by the fact that broadcast is an expensive resource, they focus on so-called broadcast optimal MPC, i.e., they give tight characterizations of which security guarantees are achievable, if broadcast is available in the first round, the second round, both rounds, or not at all.

This work considers the natural question of characterizing broadcast optimal MPC in the plain model where no set-up is assumed. We focus on 4-round protocols, since 4 is known to be the minimal number of rounds required to securely realize any functionality with black-box simulation. We give a complete characterization of which security guarantees, (namely selective abort, selective identifiable abort, unanimous abort and identifiable abort) are feasible or not, depending on the exact selection of rounds in which broadcast is available.