# [Busec] busec this week: Zhenming Liu (TIME CHANGED to **Mon 11am**) and Abhradeep Thakurta (Wed 10am)

Sharon Goldberg goldbe at cs.bu.edu
Sun Dec 15 23:09:49 EST 2013

*** Zhenming Liu's talk on Oblivious RAM will be at 11am tomorrow***

Sorry for the last minute change, but we just realized that there is a
collision between our seminar and an OS security talk at BU tomorrow at
10AM.  So, we have moved Zhenming Liu's talk to 11AM.  Just before
Zhenming's talk at 10AM, Chris Hawblitzel from MSR will talk about formal
verification of secure applications (in MCS148).

Finally, a reminder that on Wednesday December 18 Abhradeep Thakurta will
give a talk on new results in differential privacy.

Abstracts for all three talks are below.

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

****
Title: Statistically-secure ORAM with $\tilde{O}(\log^2 n)$ Overhead
Speaker: Zhenming Liu, Princeton University
Monday, December 16, 11am – 12:00am
*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.

****

END-TO-END VERIFICATION OF SECURE APPLICATIONS:
CHRIS HAWBLITZEL, MSR
STARTS:10:00 am on Monday, December 16, 2013
ENDS:11:00 am on Monday, December 16, 2013
LOCATION:MCS 148

Abstract: Projects like seL4 and Verve have demonstrated the practicality
of formally verifying the correctness of low-level operating system code
and low-level run-time system code. In this talk, I'll describe how we're
formally verifying high-level secure applications running on verified
low-level code, producing an end-to-end verified system that correctly
implements high-level application properties using low-level assembly
language instructions. I'll focus on how we compile application code,
written in the high-level language Dafny, to verified assembly language,
and how we connect the verified compiled code to a verified garbage
collector and verified OS services, provided by the Verve operating system.

Bio: Chris Hawblitzel is a Researcher in the operating systems group at
Microsoft Research. He received a B.A. in physics from UC-Berkeley in 1993,
a Ph.D. in computer science from Cornell in 2000, and was an Assistant
Professor at Dartmouth College from 2000 to 2004. At Microsoft, he
currently works on compiler and operating system verification.

****

[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
m->\infty.

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
(regret).

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/20131215/69c261a3/attachment.html>