International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Suvradip Chakraborty , Visa Research
Chaya Ganesh , Indian Institute of Science
Pratik Sarkar , Boston University
DOI: 10.1007/978-3-031-30545-0_9 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: 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 construct poly(k) maliciously-secure OTs using O(k) public key operations and O(1) inexpensive symmetric key operations, where k 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.
  title={Reverse Firewalls for Oblivious Transfer Extension and Applications to Zero-Knowledge},
  author={Suvradip Chakraborty and Chaya Ganesh and Pratik Sarkar},