Cryptology ePrint Archive: Report 2021/256

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

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

Abstract: 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.

Category / Keywords: cryptographic protocols / Non Interactive Multi-Party Computation, Fairness, Time Capsules, Blockchain Model

Original Publication (with minor differences): PETS

Date: received 2 Mar 2021, last revised 29 Jul 2021

Contact author: ghada almashaqbeh at uconn edu, fabrice benhamouda at gmail com, tal at cs columbia edu, talrny at yahoo com, abhishek shah at columbia edu, et2555 at columbia edu

Available format(s): PDF | BibTeX Citation

Version: 20210729:204829 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]