<div class="gmail_quote"><div class="gmail_quote">All, </div><div class="gmail_quote"> </div><div class="gmail_quote">Reminder for Ben Fuller&#39;s talk on computational fuzzy extractors tomorrow,  ***Friday at 10AM***.   Lunch will be provided, see you all there!</div>


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

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