<div><span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">Hi All, </span></div><div><span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif"><br>

</span></div><div><span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">This Friday, we will have </span><span style="background-color:rgb(255,255,255);color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.666666984558105px">Mahnush Movahedi from University of New Mexico speaking. We will meet at our usual time <b>10:00am to 12:00pm Friday (Nov. 9th) </b>morning, and place <b>STATA G 825</b>. </span></div>
<div><span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif"><br></span></div><div><span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">Title: Breaking the $O(nm)$ Bit Barrier: Secure Multiparty Computation</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">with a Static Adversary</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">
<br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif"><span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">In this talk, we describe a new scalable algorithm that can solve</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">Secure Multi-Party Computation (SMPC) over n players, with strictly</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">less than a 1/3 fraction of the players controlled by a static</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">adversary, and synchronous communication. For any function that can be</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">computed by a circuit with m gates, our algorithm requires each player</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">to send a number of bits and perform an amount of computation that are</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">both soft-O((n+m)/n+√n). This result significantly improves over past</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">results, which require each player to send a number of messages and</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">perform computation that are both θ(nm). We also consider a model</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">where all players are selfish but rational. In this model, we describe</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">a protocol that is a Nash equilibrium, solves SMPC, and requires each</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">player to send a number of bits and perform an amount of computation</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">that is soft-O((n+m)/n). Currently, we are working on adapting  our</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">algorithms to a fully asynchronous model, where at most a 1/4 fraction</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

<span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">of the players are bad.</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">
<br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif"><span style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">This is joint work with Varsha Dani, Valerie King and Jared Saia</span><br style="color:rgb(34,34,34);font-size:12.666666984558105px;font-family:arial,sans-serif">

</div><div><br></div>Best, <div>Rachel <br><br><div class="gmail_quote"><br></div>
</div>