[Busec] busec next week: Zhenming Liu (Mon 10am) and Abhradeep Thakurta (Wed 10am)

Sharon Goldberg goldbe at cs.bu.edu
Fri Dec 13 18:38:20 EST 2013

We end the semester next week with two exciting talks.  On Monday December
16, Zhenming Liu will present a new analysis of an ORAM scheme, and on
Wednesday December 18 Abhradeep Thakurta will give a talk on new results in
differential privacy.  Abstracts below, and lunch will be provided.


 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

Title: Statistically-secure ORAM with $\tilde{O}(\log^2 n)$ Overhead
Speaker: Zhenming Liu, Princeton University
Monday, December 16, 10am – 11:30am
*HARIRI INSTITUTE*, Room MCS180, 111 Cummington St, Boston MA

We demonstrate a simple, statistically secure, ORAM with computational
overhead $\tilde{O}(\log^2 n)$; previous ORAM protocols achieve only
computational security (under computational assumptions) or require
$\tilde{\Omega}(\log^3 n)$ overheard. An additional benefit of our ORAM is
its conceptual simplicity, which makes it easy to implement in both
software and (commercially available) hardware.

Our construction is based on recent ORAM constructions due to Shi, Chan,
Stefanov, and Li (Asiacrypt 2011) and Stefanov and Shi (ArXiv 2012), but
with some crucial modifications in the algorithm that simplifies the ORAM
and enable our analysis. A central component in our analysis is reducing
the analysis of our algorithm to a ``supermarket' problem; of independent
interest (and of importance to our analysis,) we provide an upper bound on
the rate of ``upset'' customers in the ``supermarket'' problem.


[Privacy Year Event]
Title: (Nearly) Optimal Differentially Private Singular Subspace Computation
Speaker: Abhradeep Guha Thakurta, Stanford University and Microsoft Research
Wednesday, December 18, 10am – 11:30am
MCS137, 111 Cummington St, Boston MA

Abstract: In this work we study the problem of releasing the principal
rank-k right singular subspace for a given matrix A\in R^{m x n} while
preserving differential privacy. We study the problem in the context where
each row of A is the private information belonging to an individual. We
show that there exists an (\epsilon,\delta)-differentially private
algorithm that can capture almost all the variance of A captured by  the
true principal rank-k right singular subspace, up to an additive error of
O(k\sqrt n). We further show that the error can be significantly improved
if the eigen spectrum of A^T A has a gap of \omega(\sqrt n) between k-th
and (k+1)-th eigen values. As a corollary, we show that under the eigen gap
above, the private subspace converges to the non-private subspace as

We also study the subspace estimation problem in the online setting, where
the rows of the matrix arrive online. Using a variant of the Follow the
Perturbed Leader algorithm of Kalai and Vempala, 2005, we manage to obtain
a differentially private algorithm which has (nearly) optimal error

Finally, using the recent lower bounding technique of Bun, Ullman and
Vadhan, 2013, we show that our results are essentially tight, both in the
offline and the online setting.

Joint work with: Cynthia Dwork, Kunal Talwar and Li Zhang.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20131213/706bd547/attachment.html>

More information about the Busec mailing list