Paper 2023/1677

Multi-Theorem Fiat-Shamir Transform from Correlation-Intractable Hash Functions

Abstract

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 𝑐𝑜𝑟𝑟𝑒𝑙𝑎𝑡𝑖𝑜𝑛 𝑖𝑛𝑡𝑟𝑎𝑐𝑡𝑎𝑏𝑙𝑒 ℎ𝑎𝑠ℎ 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑓𝑜𝑟 𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑙𝑦 𝑠𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝑟𝑒𝑙𝑎𝑡𝑖𝑜𝑛𝑠. The transform requires the starting protocol to be a special 3-round public-coin scheme that Canetti et al. call 𝑡𝑟𝑎𝑝𝑑𝑜𝑜𝑟 𝑠𝑖𝑔𝑚𝑎-𝑝𝑟𝑜𝑡𝑜𝑐𝑜𝑙. 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 (modeled 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.