‘Insurance’ for Computations on Secret Data
In today’s blog post I will try to explain a recent work by Bernardo David, Rafael Dowsley and myself. As usually, I will try to explain it for a non-specialist and therefore not go into technical details. Thus, instead of explaining what our paper exactly does and how it is an improvement over previous work, I’ll give a big picture of the problem that it solves. And this big picture today involves Mr. T, the FBI, money and — rather surprisingly — fairness.
Let’s imagine there has been a huge scandal recently, let’s call it X, and a certain person called Mr. T has been implicated to be part of X. It’s about tax money, it’s about organized crime, you name it. X is such a huge thing that different branches of the government are investigating it. The FBI has a look at the organized crime-side of it, while the IRS (the part of the government which collects taxes and comes after you if you don’t pay yours) investigates people who are involved in X and may have committed tax fraud. Both the FBI and the IRS may therefore have an ongoing investigation about Mr. T, so they want to find out if they should join forces and share information.
So how can they be sure that the other side is also investigating? Well, the simplest solution is for the IRS to send an e-mail to the FBI reading “Do you investigate Mr. T for X? Because we do.” but this comes with a problem: even if the FBI is not investigating, it does learn that the IRS indeed does that. But actually it should not know that — this information should be kept secret unless both of them investigate. So how can this be achieved?
The curtain rises for: Secure Multiparty Computation
Solving this aforementioned problem falls into the scope of a field of research in cryptography which is also known as Secure Multiparty Computation (MPC). Here, we have a group of n parties, each with their own input which they wish to keep secret. MPC itself is a set of algorithms which exchange messages between these n parties in order to compute an arbitrary function (or algorithm) on these inputs. The parties obtain the output of the function without learning anything beyond it. Furthermore, some flavors of MPC (such as the ones we will discuss later) achieve this even when some participants actively try to disturb the computation in an arbitrary way.
To see how such a tool would be helpful in this computation between FBI and IRS, let us describe the above setting mathematically: implicitly we can think of the FBI having a variable a. a is 1 in the case that “FBI investigates Mr. T for X” and 0 otherwise. Likewise, IRS has a variable b which is 1 if “IRS investigates Mr. T for X” and 0 otherwise. In addition, let us define the variable c which is 1 if and only if “Both FBI and IRS investigate Mr. T for X”. In the beginning, FBI knows the value of a and IRS knows the value of b. Both wish to actually compute and learn the value c, without giving their input away.
We can write up the function f which both parties wish to compute as a table (see above), where the rows reflect the value of a and the columns the value of b. Then, by looking at the intersection of the two we see the value of c. For example, if a=0 and b=1 we only have investigation by one of the two participants, so c must be 0. If on the other hand a=b=1 we see that c must be 1 as well. This coincides with the table which was given in the first figure above and which describes the setting in words. As a side note: in computer science this function is also called the logical AND function. It immediately follows that any MPC scheme which can compute the AND between two parties securely can be used in the above setting.
The Problem of Fairness
Now we know that MPC schemes exist (you can actually download and play with them!), what is the point of our paper? The problem is a property of such a computation which is called fairness. An MPC scheme is called fair if, whenever the bad guys get the output of the computation, the good guys get it as well. This seems important here, as the goal in our running example is that both IRS and FBI learn the output bit c. In his seminal work, Cleve (1986) showed that for certain numbers of misbehaving parties and certain functions, no protocol can compute the output securely and in a fair way. Unfortunately, this result particularly applies to the setting of two-party computation (as in our case).
While this might be less of a problem in our specific motivation, it’s a big issue for other applications: consider an MPC scheme which negotiates the price between farmers and a buying agent. While MPC allows to compute the economically optimal terms for the contract securely, without fairness it might happen that the agent can prevent the output to be sent to the farmers if he thinks its too low. Furthermore, he could then ask the farmers to rerun the computation due to a technical glitch and use inputs to it which are more beneficial for him. The benefits of using secure computation are lost in such a setting.
To mitigate this threat, one can rely on the next-best solution: MPC with monetary punishments or “Insured MPC”. For this to be possible, one needs an MPC scheme which delivers an unforgeable “proof” to a participating party that another party has cheated. If misbehavior is detected, the party can then ask an independent third mediator to punish the cheater by taking money from him and giving it to the victim. This way, while the definition of fairness is not achieved per se, a rational participant would refrain from defecting if the price of it is too high.
Building Insured MPC
Our construction of Insured MPC is based on previous works, but extends it in certain ways and makes it more practical at the same time. For this, we need two additional ingredients: a Distributed Ledger (DL) and a Smart Contract (SC).
A DL can be thought of as a collection of public and unforgeable bank accounts. It allows participants to send money from one to the other without ever being able to spend it twice. At the same time, it ensures that transactions from the past cannot be invalidated. A famous example of this technology is the Blockchain of Bitcoin.
SCs are autonomous programs which run on top of a DL. These are public algorithms which are run when certain conditions on the DL are met, and which then alter the data on the DL in certain predefined ways. For example, such a SC could wait for money from 10 different clients until a certain date. If the money is sent to the SC before that date by everyone, then it is collectively forwarded to a third party. Otherwise, if someone did not pay their share in time then everyone else is reimbursed by the amount they spent. Such programs can be arbitrarily complex and e.g. Ethereum supports them.
I will now outline the 6 main steps of our scheme, which follows the outline of earlier work.
In the first step, the participants run a multiparty computation with their respective inputs. Instead of obtaining the output directly, they obtain it in a secured form where they cannot see the output, but they each have obtained a key which will later be used to unlock the output. It’s important to know that the parties will need all these keys together to reconstruct the result of the secure computation. Using the MPC we can make sure that each party obtains a copy of this ‘safe’.
In a second step, each party deposits a collateral on the DL. This money will later be lost if they cheat in the remaining steps of the protocol. Note that they do not pay the money to each other, but you can think of the SC as getting all these deposits.
In the third step, the parties send their keys to each other. If each party obtains all the correct keys then it will simply send a message to the DL that everything went fine. If all parties do that, the all collect their collateral and simply walk away.
Otherwise, each party will send their key together with proof that this indeed is the correct key to the DL. Each such proof has the crucial property that they are unable to generate a proof for an invalid or different key. Now each other party can either get the correct key for unlocking from the DL, or there will be a public proof that some party cheated.
In the fifth step, the SC evaluates all the proofs and, just like Santa Clause, will determine who has been naughty and who actually posted their correct key.
Finally, since the money was all sent to the SC to begin with, it will redistribute the money based on the checking of the proofs and depending on the outcome of step 5.
In our work, we make three different contributions for schemes which fit the above pattern:
- We formally identify which criteria are sufficient to compile an MPC scheme into the above in a black-box way. While any MPC scheme can be used by hard-coding the “safe”-generation into the computation (called “white-box” cryptography), this is not necessary in our case. We achieve this by having a conceptually different “safe” than previous work. In practice, one wants not to hard-code cryptography into other cryptographic schemes as this complicates proofs and is also quite inefficient.
- We construct a special commitment scheme (think about it as the proofs which realize the safekeeping of the keys) which is specifically tailored to our application. Note that this commitment scheme is the first with the necessary properties for our application which is also efficiently verifiable in SCs. I talked about commtiments and what they are in an earlier post. A version of this scheme has already been improved upon in follow-up work.
- We give a concrete construction for all the building blocks that are involved based on one of the most efficient state-of-the-art MPC schemes.
It the real world, the FBI may just knock on the IRS’s door and ask to work together. Also, I do not really think that financial punishments would be a sufficient deterrence in this specific motivational setting. Nevertheless, I believe that this is a step to resolve the fairness problems of secure computation in practice.