<div class="gmail_quote">All, </div><div class="gmail_quote"> </div><div class="gmail_quote">Due to a conflict with the CiS seminar at MIT, we have moved Ben Fuller&#39;s talk on computational fuzzy extractors to ***Friday at 10AM***.   Lunch will be provided, see you all there!</div>

<div class="gmail_quote"> </div><div class="gmail_quote">Sharon<br>
<br>
<br>
BUsec Calendar:  <a href="http://www.bu.edu/cs/busec/" target="_blank">http://www.bu.edu/cs/busec/</a><br>
 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>
 How to get to BU from MIT:  Try the CT2 bus or MIT&#39;s &quot;Boston Daytime<br>
 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><br>

<br>
<br>
*****<br>
Computational Fuzzy Extractors<br>
Ben Fuller, BU.<br>
Thursday May 16, 10AM<br>
MCS137<br>
<br>
Fuzzy extractors derive strong keys from noisy sources.  Their<br>
security is defined information-theoretically, which limits the length<br>
of the derived key, sometimes making it too short to be useful. We ask<br>
whether it is possible to obtain longer keys by considering<br>
computational security, and show the following.<br>
<br>
- Negative Result: Noise tolerance in fuzzy extractors is usually<br>
achieved using an information-reconciliation component called &quot;secure<br>
sketch.&quot; The security of this component, which directly affects the<br>
length of the resulting key, is subject to lower bounds from coding<br>
theory.  We show that, even when defined computationally, secure<br>
sketches are still subject to the same lower bounds.<br>
<br>
- Positive Result: We show that the negative result can be overcome by<br>
analyzing computational fuzzy extractors directly.  Namely, we show<br>
how to build a computational fuzzy extractor whose output key length<br>
equals the entropy of the source (this is impossible in the<br>
information-theoretic setting). Our construction is based on the<br>
hardness of the Learning with Errors (LWE) problem, and is secure when<br>
the noisy source is uniform or symbol-fixing (that is, each dimension<br>
is either uniform or fixed). As part of the security proof, we show<br>
that the decision version of LWE is secure when a small number of<br>
dimensions has no error.<br>
<br>
Joint work with Xianrui Meng and Leonid Reyzin.<br>
</div>