Introduction toSecure Multi-Party Computation.ppt

slide * Vitaly Shmatikov CS 380S Introduction to Secure Multi-Party Computation Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. slide * Motivation General framework for describing computation between parties who do not trust each other Example: elections N parties, each one has a “Yes” or “No” vote Goal: determine whether the majority voted “Yes”, but no voter should learn how other people voted Example: auctions Each bidder makes an offer Offer should be committing! (can’t change it later) Goal: determine whose offer won without revealing losing offers Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. slide * More Examples Example: distributed data mining Two companies want to compare their datasets without revealing them For example, compute the intersection of two lists of names Example: database privacy Evaluate a query on the database without revealing the query to the database owner Evaluate a statistical query on the database without revealing the values of individual entries Many variations Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. slide * A Couple of Observations In all cases, we are dealing with distributed multi-party protocols A protocol describes how parties are supposed to exchange messages on the network All of these tasks can be easily computed by a trusted third party The goal of secure multi-party computation is to achieve the same result without involving a trusted third party Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. slide * How to Define Security? Must be mathematically rigorous Must capture all realistic attacks that a malicious participant may try to stage Should be “abstract” Based on the desired “functionality” of the protocol, not a specific protocol Goal: d