Transcript Presentation

Secure Multiparty Computation
goes Live
Peter Bogetoft, Dan Christensen, Ivan
Damgård, Martin Geisler, Thomas Jakobsen,
Mikkel Krøigaard, Janus Nielsen, Jesper
Nielsen, Kurt Nielsen, Jacob Pagter, Michael
Schwartzbach, Tomas Toft
Barbados, 2009
Ivan Damgård
Århus University
January 14, 2008
• 1200 Danish Farmers trade production rights for sugarbeets via
an electronic auction.
• As a result, 25.000 tons worth of production rights change owner
• The market price at which trading occurs is computed by 3
servers, based on encrypted bids that are never decrypted.
• First large-scale application of Secure Multiparty Computation.
Some Background
• About 5000 Danish farmers produce sugarbeets. A farmer owns a
contract, a production right, allowing him to produce a certain quantity of
beets.
• Beets are delivered to Danisco, the only Danish sugar producer.
• Recently EU drastically reduced support for production, as a result
urgent need to move production to places where it pays best.
• Hence need for a nation wide-market where production rights can be
traded.
• Decision: use a double auction.
Double Auction
Some commodity is traded. Many sellers, many buyers.
Each bid from a seller is a list of numbers: ”At each possible price per unit,
I want to sell this much” – similar for buyers. Send to auctioneer.
For each possible price, auctioneer add up bids to find total supply, and
total demand in the market at that price.
quantity
supply
demand
Market clearing price
price/unit
Demand goes down, supply up with increasing price, so can find solution
by binary search: number of comparisons logarithmic in number of
prices.
Everybody gets to sell or buy the quantity they were willing to sell or
buy at the mcp.
Privacy of Bids – Who should be auctioneer?
In the sugar beet case, privacy of bids is crucial. Bids reveal private
information about a farmer’s economy. In survey, 75% said it was important
to them that bids were confidential.
Information on farmers’ ecomic situation can be misused by Danisco 
Danisco cannot be auctioneer
Farmers could do it themselves? No, Danisco wants some control, some
farmer’s owe Danisco money, contracts act as security. Besides, farmers do
not all trust each other..
Hire a consultancy house to be auctioneer? No, too expensive
Solution chosen: do an electronic double auction, with ”virtual auctioneer”,
implemented by Danisco, DKS (farmer’s organization) and the SIMAP
research project, using multiparty computation.
Multiparty computation, intuition
m input clients I1,...,Im and n servers P1, P2, …, Pn
Usually m large, n small (ex. m=1500, n=3)
Player Ii submits input xi in appropriately encrypted form
By collaborating, P1,..Pn compute y= f(x1,…,xm) for some function f.
Must be be done securely, i.e.,
• All learn the correct value of y
• Nothing except y is made public. In particular no input is decrypted,
and no Pi gets access to any information on the inputs.
P1,.., Pn implement a ”virtual trusted party”
Computation needed
Lots of additions to find total demand/supply at each price.
Some comparisons to do binary search for market clearing price.
Comparison results can be public, follow anyway from value of
market clearing price.
Protocols Used
Based on Shamir Secret sharing modulo a sufficiently large prime p (65
bits in our case). Notation: [c] means c, secret shared.
• Addition and multiplication easy using standard tools
• Comparison a bit harder..
Comparison ct’d
Problem: hard to go from [c] to [c0], [c1],…, [cn] where [ci] is i’th bit of c.
Observation [from Damgård et al TCC 07] : much easier go from
[c0], [c1],…, [cn] to [c] since Shamir secret sharing is linear - just multiply
by 2-powers and add.
Suppose we know a,b are at most t-bit numbers.
Algorithm
1. Generate random shared 0/1 values [r0],…., [rv], compute [r], where
r= r0+ 2 r1 + … + 2vrv v chosen so r >> a,b
2. Compute and open T= r + 2t +a – b (statistically secure since r >> a,b).
3. Remaining problem: if we subtract bit-wise shared number r from the
public T, will bit no. t be set? Hence enough to do a linear (in t) number of
binary operations.
In paper: technique to do this in logarithmic number of rounds.
How to deliver inputs
The obvious idea: client secret shares each input number and encrypts all
shares intended for Pi under his public key
Communication becomes linear size in number of servers, to encrypt B bits,
must send O(nB) bits
In paper: Technique to encrypt shares such that only an additive overhead
depends on number of servers, need to send O(n) + O(B) bits.
Implementation Architecture
SIMAP
Danisco
SIMAP webserver
session
DB
LAN
log-in
Danisco
Java-applet
Encrypted
bid
farmer
Submitting bids
DKS
beregning
Implementation Architecture
SIMAP
Danisco
SIMAP webserver
session
DB
DB
LAN
log-in
Danisco
Java-applet
Encrypted
bid
Farmer
Submitting bids
DKS
DB
Computation
DB
Performance 1
Performance 2
Why Multiparty Computation?
If some party has access to the private data in the clear, everone has to
agree on a security policy: who is allowed access, and when? Who is held
responsible if data leaks and what are the consequences?
 Difficult negotiations because parties have conflicting interests, could
have halted the entire project.
 Nobody wanted the responsibility of having to store the bids in clear.
These concerns seem more important than fear of malicious attack by the
“opponent” => security against malicious attacks seems less important.
With multiparty computation, bids are kept protected at all times, hence
easier to communicate security policy to the farmers.
An MPC based software solution can be developed and scrutinized once and
cost can be amortized over several applications. In contrast, having a
consultancy house be trusted party costs a fee every time.
Use secure hardware instead?
This is also a single trusted party solution! Even if hardware
protection cannot be broken, security depends on how the hardware
box is administrated, maintained, backed up etc.
Hence we still need to agree on a common security policy.
Seems more natural for players to use hardware to improve their own
security
In Conclusion..
Applications of MPC can be realized with the efficiency and functionality
that is required in real life.
Ability of MPC to keep private data secret to everyone, really is useful in
practice.
More applications?
I think yes, but give it time!
Compare to Digital signatures: invented in 1977, first nation-wide system in
Denmark started 2 years ago!
More info on research projects, see
www.sikkerhed.alexandra.dk/uk/projects/simap.htm
New spin-off by the SIMAP people
www.partisia.com
Attacks
External attacks: need to handle those, but similar issues and solutions as
lots of other applications..
Attacks by bidders
Can protect against malicious bidders, we decided the risk was too low to
motivate cost.
Attacks by parties doing the computation
No party seriously suspected others of a malicious attack,
BUT not acceptable to give all the bids to the opponent
AND nobody wanted the responsibility of dealing with the private data.
Would lead to earlier mentioned problems with agreeing on security policy
etc.
Hence we went for semi-honest security.