Paper 2023/1677

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

Michele Ciampi, University of Edinburgh
Yu Xia, University of Edinburgh
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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACNS 2023
DOI
10.1007/978-3-031-33491-7_21
Keywords
NIZKFiat-Shamir TransformAdaptive Multi-Theorem Zero-KnowledgeCorrelation Intractable Hash Functions
Contact author(s)
michele ciampi @ ed ac uk
yu xia @ ed ac uk
History
2023-10-30: approved
2023-10-30: received
See all versions
Short URL
https://ia.cr/2023/1677
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1677,
      author = {Michele Ciampi and Yu Xia},
      title = {Multi-Theorem Fiat-Shamir Transform from Correlation-Intractable Hash Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1677},
      year = {2023},
      doi = {10.1007/978-3-031-33491-7_21},
      url = {https://eprint.iacr.org/2023/1677}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.