# [Busec] busec this week: Ben Fuller (Thurs 11am)

Sharon Goldberg goldbe at cs.bu.edu
Mon Mar 31 20:38:42 EDT 2014

Since most of our group is still away in warm Spanish-speaking countries,
seminar this week will be at an UNUSUAL TIME: Thursday at 11am.  Ben Fuller
will be talking about his PhD proposal: key derivation from noisy sources.
We will have lunch in the lab after the talk.

The following week, we have a talk by Jamie Morgenstern (at the usual time)
as part of our privacy year series.

See you there!

Sharon

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: The CT2 bus or MIT's "Boston Daytime Shuttle"
http://web.mit.edu/facilities/transportation/shuttles/daytime_boston.html

****

Key Derivation From Noisy Sources With More Errors Than Entropy
Ben Fuller. BU.
Thu, April 3, 11am - 12pm
MCS 137

(This is also Ben's PhD proposal!)

Fuzzy extractors convert a noisy source of entropy into a consistent
uniformly-distributed key. In the process of eliminating noise, they lose
some of the entropy of the original source--in the worst case, as much as
the logarithm of the number of correctable error patterns. We call what is
left after this worst-case loss the minimum usable entropy. Unfortunately,
this quantity is negative for some sources that are important in practice.
Most known approaches for building fuzzy extractors work in the worst case
and cannot be used when the minimum usable entropy is negative.

We construct the first fuzzy extractors that work for a large class of
distributions that have negative minimum usable entropy. Their security is
computational. They correct Hamming errors over a large alphabet. In order
to avoid the worst-case loss, they necessarily restrict distributions for
which they work.

Our first construction requires high individual entropy of a constant
fraction of symbols, but permits symbols to be dependent. Our second
construction requires a constant fraction of symbols to have a constant
amount of entropy conditioned on prior symbols. The constructions can be
implemented efficiently based on number-theoretic assumptions or
assumptions on cryptographic hash functions.

Joint work with Ran Canetti,  Omer Paneth, and Leonid Reyzin.

***

Privacy-Preserving Public Information for Sequential Games
Jamie Morgenstern, CMU
Wed, April 9, 10am - 11:30am
MCS137

In settings with incomplete information, players can find it
difficult to coordinate to find states with good social welfare. For
example, in financial settings, if a collection of financial firms
have limited information about each other's strategies, some large
number of them may choose the same high-risk investment in hopes of
high returns. While this might be acceptable in some cases, the
economy can be hurt badly if many firms make investments in the same
risky market segment and it fails. One reason why many firms might
end up choosing the same segment is that they do not have
information about other firms' investments (imperfect information
investments, however, raises confidentiality concerns for both
individuals and institutions.

In this paper, we explore whether information about the game-state
can be publicly announced in a manner that maintains the privacy of
the actions of the players, and still suffices to deter players from
reaching bad game-states. We show that in many games of interest, it is
possible for players to avoid these bad states with the help of
\emph{privacy-preserving, publicly-announced information}. We model
behavior of players in this imperfect information setting in two ways --
greedy and undominated strategic behaviours, and we prove guarantees on
social welfare that certain kinds of privacy-preserving information can
help attain. Furthermore, we design a counter with improved privacy
guarantees under continual observation.

Joint work with Avrim Blum, Adam Smith, and Ankit Sharma
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20140331/7aaa3b9b/attachment.html>
`