Secure Multiparty Computation (SMC) is a technology that allows you to compute on
encrypted * numbers. This might sound impossible at first - but in fact, by using the right kind of
cryptography *, it is not.
SMC allows a number of servers to jointly compute any function without learning the inputs to the function. As an example, SMC allows a number of servers to jointly compute the result of an auction without learning the bids submitted to the auction. This is achieved by providing each server with only partial information on each bid. The partial information given to a single server (in some cases even several servers) reveals nothing about the actual bid. Nevertheless, using the right cryptographic tools, the servers can work together and compute the result.
Secret sharing
One such cryptographic tool is called secret sharing. Suppose that a secret
x=42 is to be shared among 2 servers. If we choose two random numbers
x1 and
x2 such that
x=
x1+
x2 (e.g.
x1=50 and
x2= -8) and give
x1 to the first server and
x2 to the second, then neither server will know the secret
x. Indeed, the first server only learns the number 50, and from its point of view, the other number could be any integer. Of course, 50 + anything can result in anything.
Similarly we might secret share another number y=23 between the two servers (e.g. y1=20 and y2=3). The two servers can now compute x+y and make this, without either server learning x nor y. The first server simply computes x1+y1 and sends the result to the second server, which can then compute x1+y1+x2+y2=x+y - all of this without any server learning anything about x nor y, other than the sum.
Any function
A central result in cryptography is that the ideas behind secret sharing can be extended to allow the computation of any function that a traditional computer can compute. Of course, due to the fact that computation is distributed across a number of servers, performance suffers.
The technological building block behind Partisia Market Design is a robust and efficient implementation of these cryptographic ideas. This implementation provides confidentiality * of encrypted * data to a level that corresponds to modern commercial cryptographic primitives such as RSA and AES.
Deep confidentiality
Securing input confidentiality in a computation like an auction would traditionally (without SMC) be done in two seperate steps: 1) encrypting the bids in transit from the bidder to the auctioneer (but decrypted when they arrive at the auctioneer), and 2) ensuring that the auctioneer keeps the bids confidential. The latter is normally ensured by enforcing security policies restricting which employees of the auctioneer have access to the bids and when. Unfortunately, this latter step is notoriously hard, and consequently the realized solution only provides
shallow confidentiality *.
Using secure multiparty computation this latter part can be entirely avoided. Bids are never decrypted. No complex security policies are required. We call this deep confidentiality *.
This is the essence of secure multiparty computation. It provides a high degree of security, simple administration and consequently efficient deployment of solutions needed for confidential handling of data.
See here for more information about why Confidentiality >> is important and how secure multiparty computation allows us to address Collusion >>
References