Paper 2021/256

Gage MPC: Bypassing Residual Function Leakage for Non-Interactive MPC

Ghada Almashaqbeh, Fabrice Benhamouda, Seungwook Han, Daniel Jaroslawicz, Tal Malkin, Alex Nicita, Tal Rabin, Abhishek Shah, and Eran Tromer


Existing models for non-interactive MPC cannot provide full privacy for inputs, because they inherently leak the residual function (i.e., the output of the function on the honest parties’ input together with all possible values of the adversarial inputs). For example, in any non-interactive sealed-bid auction, the last bidder can figure out what was the highest previous bid. We present a new MPC model which avoids this privacy leak. To achieve this, we utilize a blockchain in a novel way, incorporating smart contracts and arbitrary parties that can be incentivized to perform computation (“bounty hunters,” akin to miners). Security is maintained under a monetary assumption about the parties: an honest party can temporarily supply a recoverable collateral of value higher than the computational cost an adversary can expend. We thus construct non-interactive MPC protocols with strong security guarantees (full security, no residual leakage) in the short term. Over time, as the adversary can invest more and more computational resources, the security guarantee decays. Thus, our model, which we call Gage MPC, is suitable for secure computation with limited-time secrecy, such as auctions. A key ingredient in our protocols is a primitive we call “Gage Time Capsules” (GaTC): a time capsule that allows a party to commit to a value that others are able to reveal but only at a designated computational cost. A GaTC allows a party to commit to a value together with a monetary collateral. If the original party properly opens the GaTC, it can recover the collateral. Otherwise, the collateral is used to incentivize bounty hunters to open the GaTC. This primitive is used to ensure completion of Gage MPC protocols on the desired inputs. As a requisite tool (of independent interest), we present a generalization of garbled circuit that are more robust: they can tolerate exposure of extra input labels. This is in contrast to Yao’s garbled circuits, whose secrecy breaks down if even a single extra label is exposed. Finally, we present a proof-of-concept implementation of a special case of our construction, yielding an auction functionality over an Ethereum-like blockchain.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.PETS
Non Interactive Multi-Party ComputationFairnessTime CapsulesBlockchain Model
Contact author(s)
ghada almashaqbeh @ uconn edu
fabrice benhamouda @ gmail com
tal @ cs columbia edu
talrny @ yahoo com
abhishek shah @ columbia edu
et2555 @ columbia edu
2021-07-29: last of 3 revisions
2021-03-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ghada Almashaqbeh and Fabrice Benhamouda and Seungwook Han and Daniel Jaroslawicz and Tal Malkin and Alex Nicita and Tal Rabin and Abhishek Shah and Eran Tromer},
      title = {Gage MPC: Bypassing Residual Function Leakage for Non-Interactive MPC},
      howpublished = {Cryptology ePrint Archive, Paper 2021/256},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.