Basic research in cryptology has shown that it is possible to combine and process information from several sources and at the same time control exactly what information is revealed. The technique is known as secure multiparty computation (SMC), and while the first solutions suggested were very inefficient, the current state of the art allows us to perform interesting computations.
In principle, the idea is simple: all necessary data are supplied and processed in encrypted form. The results made public will therefore only be those that the involved parties agree to have decrypted. Computing without actually looking at the data may seem impossible; nevertheless this is exactly the challenge that has been solved in basic research since the late 80s.
To gain an intuition into the techniques, consider the equation gxgy = gx+y. Thinking of x and y as data and gx as an 'encryption' of x, we see that multiplying encryptions adds the data implicitly without accessing it. The actual solutions use similar relations, and are based on both classical number theory and basic algebraic concepts such as polynomials over finite fields.
The application scenario for the SMC techniques on which SIMAP has focused is the following. Several thousand Danish farmers produce sugar beets, which they sell to Danisco, the only Danish sugar producer. The farmers have contracts production rights entitling them to produce and deliver beets to Danisco. Contracts can be traded, and it has recently become necessary to reallocate contracts to where production pays off best. Historically, trade has been very limited, so a national market is needed to facilitate it.
A good strategy for this is a so-called double auction. Briefly, the goal is to determine the market clearing price, a price per unit at which all trade occurs. For each potential price, each party (bidder) specifies how much he would buy or sell if this were the actual price. All such bids go to an auctioneer, who determines the price where total supply equals total demand. All parties then trade their desired amounts at this price.
While a single trusted party could serve as auctioneer, this is not satisfactory in the given scenario. For instance, bids reveal information about a farmer's economic position and productivity, making farmers reluctant to accept Danisco as auctioneer. On the other hand, contracts may act as security for a farmer's debt to Danisco, whence they would not accept the farmers' association, DKS, running the auction alone. Relying on a third party such as an external consultancy house would be a very expensive option. It was therefore decided to use SMC, which allows the double auction to be run without having to place trust in a single party. The role of auctioneer is then distributed among Danisco, DKS, and SIMAP.
The system was comprised of a Web server receiving bids, and three servers performing the secure computation. Each farmer supplied his bids through an applet, which sent encrypted bids to a database. After the deadline for the auction had passed, the servers were connected to the database and to each other, and the market clearing price was securely computed along with the quantity to be traded by each bidder.
The auction had a total of 1200 participating bidders. The actual computation took place on 14 January this year and lasted about thirty minutes. The result involved around 25,000 tons of production rights changing ownership; to our knowledge this was the first large-scale and genuinely practical application of SMC.
Not only was the auction system a success from a technological point of view, but in addition the users, DKS and Danisco, were happy. Interestingly, 80% of bidders responding to a survey said that the confidentiality of their bids was important to them.
In conclusion, although practical SMC is still in its infancy, it holds great promise as a tool in many settings. This potential stems from the fact that SMC keeps secret everything that is not intended to be public. Not only does this provide confidentiality, it also short-circuits discussions about which parts of the data are sensitive, and which common security policies should apply to such data. Such discussions might well have brought the whole project to a halt if Danisco and DKS had tried to run the auction using conventional methods.
Links:
http://www.sikkerhed.alexandra.dk/uk/projects/simap/index.htm
http://www.sikkerhed.alexandra.dk/uk/projects/scet.htm
http://eprint.iacr.org/2008/068
http://www.daimi.au.dk/~buus/crypto/
http://www.cwi.nl/projects/crypto/
http://www.win.tue.nl/dw/cc/
Please contact:
Ivan Damgård
University of Aarhus, Denmark
Tel: +45 89425780
E-mail: ivan
daimi.au.dk
Tomas Toft
Eindhoven University of Technology and CWI, The Netherlands
E-mail: T.Toftcwi.nl
