Introducing ‘The World’s Billionaires Problem’
On MPC and catching cheating billionaires
(This story was originally published on the PRIViLEDGE H2020 project on Oct. 25, 2019.)
While Forbes surveys the world’s billionaires thoroughly each year, this is not always without controversy.
Two years ago, in November 2017, Forbes discovered that a prominent billionaire was listed unfairly. Former President Trump’s Commerce Secretary, Wilbur Ross, had apparently overstated his wealth. Forbes reviewed the public financial-disclosure forms filed by Mr. Ross after being nominated for Commerce secretary, and adjusted his reported wealth to $700 mln. Significantly less than the $2.9 bln he had previously reported to Forbes. “It seems clear that Ross lied to us,” Forbes wrote.
Yao’s Millionaires
The above illustrates that one of the famous problems in cryptography is still relevant today: Yao’s Millionaires’ problem, introduced in 1982 by computer scientist Andrew Yao, describes the problem of two millionaires who aim to find out who is richer without revealing their actual wealth. The problem is an analogy of a more general problem, namely comparing two confidential values. Cryptographers use the term ‘Secure Computation’ or ‘Secure Multiparty Computation’ (MPC) to refer to these methods that compute a function while keeping the inputs private.
Since the eighties, the theory of MPC and its applications have evolved rapidly. In this article, we’d like to highlight one particular development, namely that of Verifiable MPC. We will explain briefly what it is, illustrate the benefits and present a relevant application in the blockchain context.
Today, MPC is applied in blind (sealed-bid) auctions and population studies. For example, the first deployment of MPC at scale was by Danisco and the association of Danish sugar beet growers. When a reduction in EU subsidies drove the need to trade production rights, a blind auction between beet growers was implemented by using MPC.
Verifiable MPC with blockchain
Typically, in an MPC setting, the parties that provide input are also part of the computation. However, one can also imagine a scenario where the input is external to the computation. For example, in the blockchain context, imagine a scenario where players in an auction post their bids (to a smart contract) on a blockchain and outsource the secure computation to a network of MPC parties. These MPC parties, who are external to the blockchain, download the private inputs from the chain, compute the auction result and post it back to the chain. The benefit of this model is that the smart contract does not have to carry the heavy load (and cost) of computation and storage. (Note: The idea of outsourcing a smart contract computation to MPC workers is not new. To our knowledge, this concept was first suggested by Zyskind, Nathan and Pentland in 2015.)
The World’s Billionaires Problem
Let’s introduce a hypothetical problem, underscored by our opening paragraph of wannabe billionaires. We propose an extension of Yao’s famous Millionaires’ problem and coin it ‘the World’s Billionaires Problem’. In Yao’s problem, the millionaires can still provide false inputs to the computation, so it does not fully address the scenario of Mr. Ross. In addition to Yao’s version, we require that the inputs and outputs are verifiable. More specifically, the inputs are encryptions of everybody’s tax returns (voluntarily provided), signed for correctness by the tax authority and posted on the blockchain. The output should be a public ranking of the top 400 billionaires world-wide with a proof of correctness. The end-to-end computation needs to ensure privacy for all but the top 400. (I.e., MPC parties and parties querying the blockchain learn nothing but the top 400.)
Two cryptographic protocols
We highlight two cryptographic protocols that are used to make this example work in practice. First, we need a protocol to convert an encrypted input (posted on the chain) to secret inputs for MPC parties, (so called ‘secret shares’). Second, we need an MPC protocol that verifies whether the inputs are well-formed, calculates the result, and returns the result with a cryptographic proof that the computation was performed correctly. We call this a Verifiable MPC protocol. The latter requirement, the proof of correctness, is particularly relevant in the blockchain context where we want to reduce the trust in third parties to a minimum. With such a proof, the users of the smart contract have the guarantee that the MPC workers did not tamper with the calculation. This proof is created in zero-knowledge, meaning that the parties can convince a verifier of the correctness without revealing anything about the private inputs.
Academic work
The second protocol highlighted above can be realized using the Trinocchio (2015) and Geppetri (2017) protocols developed by Veeningen et al. Both results build on the now-famous Pinocchio (ZK-SNARK) protocol from 2013 by Parno, Howell, Gentry and Raykova. We refer to a presentation on the Priviledge website for a walk-through of the protocol.
The first protocol highlighted above (the conversion from one encryption to secret inputs to MPC parties) is part of ongoing research at TU Eindhoven. We are pleased to announce that we have a working prototype and a draft paper that we are planning to publish in the coming months as part of the PRIViLEDGE project deliverables — If you have questions in the meantime, please feel free to contact us.
Conclusion and next steps
With the two protocols presented above, combined with the immutability of a blockchain, we believe we have provided critical components to solve ‘the World’s Billionaires Problem’: verifiable (and immutable) inputs, private computation on these inputs and verifiable outputs. One topic that we have not touched on in this blog is the complexity of doing (many) secure comparisons verifiably in MPC, which is something we are actively researching. We are happy to hear from you if you are interested in our work.
Written by Eindhoven University of Technology, Berry Schoenmakers (e-mail: l.a.m.schoenmakers@tue.nl) & Toon Segers (e-mail: a.j.m.segers@tue.nl)
