[Busec] BUsec this week: Ben Fuller (NEW TIME: Fri 10AM)

Sharon Goldberg goldbe at cs.bu.edu
Thu May 16 21:49:21 EDT 2013


Reminder for Ben Fuller's talk on computational fuzzy extractors tomorrow,
***Friday at 10AM***.   Lunch will be provided, see you all there!


BUsec Calendar:  http://www.bu.edu/cs/busec/
 BUsec Mailing list:  http://cs-mailman.bu.edu/mailman/listinfo/busec
 How to get to BU from MIT:  Try the CT2 bus or MIT's "Boston Daytime

Computational Fuzzy Extractors
Ben Fuller, BU.
Thursday May 16, 10AM

Fuzzy extractors derive strong keys from noisy sources.  Their
security is defined information-theoretically, which limits the length
of the derived key, sometimes making it too short to be useful. We ask
whether it is possible to obtain longer keys by considering
computational security, and show the following.

- Negative Result: Noise tolerance in fuzzy extractors is usually
achieved using an information-reconciliation component called "secure
sketch." The security of this component, which directly affects the
length of the resulting key, is subject to lower bounds from coding
theory.  We show that, even when defined computationally, secure
sketches are still subject to the same lower bounds.

- Positive Result: We show that the negative result can be overcome by
analyzing computational fuzzy extractors directly.  Namely, we show
how to build a computational fuzzy extractor whose output key length
equals the entropy of the source (this is impossible in the
information-theoretic setting). Our construction is based on the
hardness of the Learning with Errors (LWE) problem, and is secure when
the noisy source is uniform or symbol-fixing (that is, each dimension
is either uniform or fixed). As part of the security proof, we show
that the decision version of LWE is secure when a small number of
dimensions has no error.

Joint work with Xianrui Meng and Leonid Reyzin.

Sharon Goldberg
Computer Science, Boston University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20130516/2f94a294/attachment.html>

More information about the Busec mailing list