publications

2023

1. ACNS2023

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

   Michele Ciampi, and Yu Xia

   In Applied Cryptography and Network Security: 21st International Conference, ACNS 2023, Kyoto, Japan, June 19–22, 2023, Proceedings, Part II, Kyoto, Japan, 2023

   Abs DOI Bib HTML

   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.

   @inproceedings{ACNS:CiaXia23,
     title = {Multi-Theorem Fiat-Shamir Transform from Correlation-Intractable Hash Functions},
     author = {Ciampi, Michele and Xia, Yu},
     booktitle = {Applied Cryptography and Network Security: 21st International Conference, ACNS 2023, Kyoto, Japan, June 19--22, 2023, Proceedings, Part II},
     editor = {Tibouchi, Mehdi and Wang, XiaoFeng},
     publisher = {Springer Nature Switzerland},
     address = {Cham},
     isbn = {978-3-031-33491-7},
     url = {https://link.springer.com/chapter/10.1007/978-3-031-33491-7_21},
     doi = {10.1007/978-3-031-33491-7_21},
     pages = {555--581},
     year = {2023},
     numpages = {27},
     keywords = {Fiat-Shamir Transform, NIZK, Correlation Intractable Hash Functions, Adaptive Multi-Theorem Zero-Knowledge},
     location = {Kyoto, Japan},
     dimensions = {true},
   }

2. TCC2023

   Broadcast-Optimal Four-Round MPC in the Plain Model

   Michele Ciampi, Ivan Damgård, Divya Ravi, and 3 more authors

   In Theory of Cryptography: 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 – December 2, 2023, Proceedings, Part II, 2023

   Abs DOI Bib HTML Video

   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.

   @inproceedings{TCC:CDRSXY23,
     author = {Ciampi, Michele and Damg{\aa}rd, Ivan and Ravi, Divya and Siniscalchi, Luisa and Xia, Yu and Yakoubov, Sophia},
     editor = {Rothblum, Guy and Wee, Hoeteck},
     title = {Broadcast-Optimal Four-Round MPC in the Plain Model},
     booktitle = {Theory of Cryptography: 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 – December 2, 2023, Proceedings, Part II},
     year = {2023},
     publisher = {Springer Nature Switzerland},
     address = {Cham},
     numpages = {30},
     pages = {3--32},
     isbn = {978-3-031-48618-0},
     doi = {10.1007/978-3-031-48618-0_1},
     dimensions = {true},
   }