Paper 2022/1535

Reverse Firewalls for Oblivious Transfer Extension and Applications to Zero-Knowledge

Suvradip Chakraborty, Visa Research
Chaya Ganesh, Indian Institute of Science Bangalore
Pratik Sarkar, Boston University

In the setting of subversion, an adversary tampers with the machines of the honest parties thus leaking the honest parties' secrets through the protocol transcript. The work of Mironov and Stephens-Davidowitz (EUROCRYPT’15) introduced the idea of reverse firewalls (RF) to protect against tampering of honest parties' machines. All known constructions in the RF framework rely on the malleability of the underlying operations in order for the RF to rerandomize/sanitize the transcript. RFs are thus limited to protocols that offer some structure, and hence based on public-key operations. In this work, we initiate the study of $efficient$ Multiparty Computation (MPC) protocols in the presence of tampering. In this regard, - We construct the $first$ Oblivious Transfer (OT) extension protocol in the RF setting. We obtain $poly(\kappa)$ maliciously-secure OTs using $O(\kappa)$ public key operations and $O(1)$ inexpensive symmetric key operations, where $\kappa$ is the security parameter. - We construct the $first$ Zero-knowledge protocol in the RF setting where each multiplication gate can be proven using $O(1)$ symmetric key operations. We achieve this using our OT extension protocol and by extending the ZK protocol of Quicksilver (Yang, Sarkar, Weng and Wang, CCS'21) to the RF setting. - Along the way, we introduce new ideas for malleable interactive proofs that could be of independent interest. We define a notion of $full$ $malleability$ for Sigma protocols that unlike prior notions allow modifying the instance as well, in addition to the transcript. We construct new protocols that satisfy this notion, construct RFs for such protocols and use them in constructing our OT extension. The key idea of our work is to demonstrate that correlated randomness may be obtained in an RF-friendly way $without$ having to rerandomize the entire transcript. This enables us to avoid expensive public-key operations that grow with the circuit-size.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2023
SubversionReverse FirewallsOblivious Transfer ExtensionZero-Knowledge
Contact author(s)
suvradip1111 @ gmail com
chaya @ iisc ac in
pratik93 @ bu edu
2023-02-23: revised
2022-11-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Suvradip Chakraborty and Chaya Ganesh and Pratik Sarkar},
      title = {Reverse Firewalls for Oblivious Transfer Extension and Applications to Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1535},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.