<div dir="ltr">At seminar next week, Omer Paneth will talk about his new STOC paper on extractable one-way functions (Wed 10am).&nbsp; This is a preview of talk he is giving at NYC Crypto Day in a few weeks.<br><br>The following week, we have a talk by Gilad Asherov about fairness in two-party computation; Gilad&#39;s seminar will start a bit earlier than usual (9:30am Wed).<br>

<div><div><div><div class="gmail_quote"><div dir="ltr"><div><div><div class="gmail_quote"><div dir="ltr"><div class="gmail_quote"><div dir="ltr"><div><div class="gmail_quote"><div dir="ltr"><div class="gmail_quote"><div dir="ltr">

<div><br></div><div>Sharon<br></div><div><br><br>&nbsp;BUsec Calendar:&nbsp; <a href="http://www.bu.edu/cs/busec/" target="_blank">http://www.bu.edu/cs/busec/</a><br>



&nbsp;BUsec Mailing list: <a href="http://cs-mailman.bu.edu/mailman/listinfo/busec" target="_blank">http://cs-mailman.bu.edu/mailman/listinfo/busec</a><br>


&nbsp;How to get to BU from MIT: The CT2 bus or MIT&#39;s &quot;Boston Daytime Shuttle&quot; <a href="http://web.mit.edu/facilities/transportation/shuttles/daytime_boston.html" target="_blank">http://web.mit.edu/facilities/transportation/shuttles/daytime_boston.html</a></div>








<div><br></div><div>**********<br><br></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br>***********<br>On the Existence of Extractable One-Way Functions<br>Omer Paneth, BU.<br>Wed, February 12, 10am &ndash; 11am<br>

MCS137 <br>&nbsp;<br>A function f is extractable if it is possible to algorithmically &ldquo;extract,&rdquo; from any adversarial program that outputs a value y in the image of f, a preimage of y. When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions. We make two headways in the study of the existence of extractable one-way functions (EOWFs). On the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length. On the positive side, for programs with bounded auxiliary-input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zero-knowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions. <br>

<br>Joint work with Nir Bitansky, Ran Canetti and Alon Rosen.<br><br>****<br><br>Towards Characterizing Complete Fairness in Secure Two-Party Computation.<br>Gilad Asharov. Bar Ilan University. <br>Wed, February 19, 9:30am &ndash; 11:00am<br>

MCS137<br><br>The well known impossibility result of Cleve (STOC 1986) implies that in general it is impossible to securely compute a function with complete fairness without an honest majority. Since then, the accepted belief has been that nothing non-trivial can be computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist some non-trivial (deterministic, finite-domain) boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. <br>

<br>In this work we show that not only that some or few functions can be computed fairly, but rather an enormous amount of functions can be computed with complete fairness. In fact, almost all boolean functions with distinct domain sizes can be computed with complete fairness (for instance, more than $99.999\%$ of the boolean functions with domain sizes $31 \times 30$). The class of functions that is shown to be possible includes also rather involved and highly non-trivial tasks, such as set-membership, evaluation of a private (Boolean) function and private matchmaking. In addition, we demonstrate that fairness is not restricted to the class of symmetric boolean functions where both parties get the same output, which is the only known feasibility result. Specifically, we show that fairness is also possible for asymmetric boolean functions where the output of the parties is not necessarily the same. Moreover, we consider the class of functions with non-binary output, and show that fairness is possible for any finite range.&nbsp; <br>

</div></div></div></div>