[Busec] BUsec this week: Kai-Min Chung (Tues 11AM) & David Xiao (Thurs 11AM)

Sharon Goldberg goldbe at cs.bu.edu
Sun Feb 26 15:44:42 EST 2012


We have two visitors giving seminars this week:  Tuesday 11AM we have
Kai-Min Chung visiting from Cornell, and Thursday 11AM we have Dave
Xiao visiting from France.  Both seminars will be in 111 Cummington
St, but we'll move to the bigger room MCS148.

We continue next Tues with our own Ben Fuller, speaking about joint
work with Leo Reyzin and Adam ONeill.

See you there!


Title: The Randomness Complexity of Parallel Repetition
Speaker: Kai-Min Chung, Cornell
When:  Feb 28, 11AM, MCS148

Consider a $m$-round interactive protocol with soundness error $1/2$.
How much extra randomness is required to decrease the soundness error
to $\delta$ through parallel repetition? Previous work, initiated by
Bellare, Goldreich and Goldwasser, shows that for public-coin
interactive protocols with statistical soundness, $m \cdot O(\log
(1/\delta))$ bits of extra randomness suffices. In this talk, I will
present our recent work on the above question:

- We establish the first derandomized parallel repetition theorem for
public-coin interactive protocols with *computational soundness*
(a.k.a. arguments). The parameters of our result essentially matches
the earlier works in the information-theoretic setting.

- We show that obtaining even a sub-linear dependency on the number of
rounds $m$ (i.e., $o(m) \cdot \log(1/\delta)$) is impossible in the
information-theoretic, and requires the existence of one-way functions
in the computational setting.

- We show that non-trivial derandomized parallel repetition for
private-coin protocols is impossible in the information-theoretic
setting and requires the existence of one-way functions in the
computational setting.

These results are tight in the sense that parallel repetition theorems
in the computational setting can trivially be derandomized using
pseudorandom generators, which are implied by the existence of one-way

This is a joint work with Rafael Pass.

David Xiao, LIAFA France. Privacy, incentives, and truthfulness.
Thursday, March 1, 11AM, MCS148

Privacy has become an ever more pressing concern as we
conduct more and more of our lives in public forums such as the
Internet. One privacy question that has received much study is how a
database curator may output "sanitized" data that does not reveal too
much information about any particular individual.  This criteria has
been formalized as differential privacy, proposed originally by Dwork
et al. (TCC '06 and ICALP '06), which captures the idea that "the
presence or absence of any individual's data does not change the
distribution of the sanitized data by much". This guarantee has been
interpreted to mean that individuals should be comfortable revealing
their information, since their participation barely changes the

In this talk, we advocate combining the study of privacy in
conjunction with game theory, since individuals need to be motivated
by some incentive in order to part with their private information.  We
focus on the notion of truthfulness, which says that a mechanism
should be designed so that it is in the individuals' own interest to
give their true information.  We show that there exist games for which
differentially private mechanisms, in particular the exponential
mechanism of McSherry and Talwar (FOCS '07), do not motivate the
individuals to participate truthfully. On the positive side, we show
that a wide class of games do admit differentially
private, truthful, and efficient mechanisms.

Finally, we explore the possibility of tradeoffs between utility and
privacy.  This is because individuals may be willing to give up some
privacy if they receive enough utility from a game, and vice versa. We
show that, under a natural measure of information cost, certain
differentially private mechanisms such as releasing a differentially
private histogram or a differentially private synthetic database may
reveal so much information that individuals would rather suffer the
consequences of lying rather than have their information published

Ben Fuller. BU. A unified approach to deterministic encryption


Public Key Encryption is a ubiquitous cryptographic tool.  A
randomized encryption algorithm is necessary to achieve semantic
security.  However, in several applications a deterministic encryption
algorithm is necessary or enables additional functionality.

In this talk, we present a general construction of deterministic
encryption schemes that unifies prior work and gives novel schemes. We
focus on a single message instantiation based on any trapdoor function
that has sufficiently many hardcore bits.  Our work also provides a
construction that achieves "bounded" multi-message security from lossy
trapdoor functions through a generalization of the leftover hash
lemma.  Our single message scheme is enabled by two tools that are of
broader interest:

- A weaker and more precise sufficient condition for "semantic"
security on a high-entropy message distribution. Namely, we show that
to establish "semantic" security on a distribution M of messages, it
suffices to establish indistinguishability for all conditional
distribution M|E, where E is an event of probability at least 1/4.
(Prior work required indistinguishability on all distributions of a
given entropy.)

- A result about computational entropy of conditional distributions.
Namely, we show that conditioning on an event E of probability p
reduces the quality of computational entropy by a factor of p and its
quantity by log_2 1/p.  We also extend our result about computational
entropy to the average case, which is useful in reasoning about
leakage-resilient cryptography: leaking \lambda bits of information
reduces the quality of computational entropy by a factor of 2^\lambda
and its quantity by \lambda.

Joint work with Adam ONeill and Leo Reyzin.

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list