[Colloquium] CS Seminar Nov. 28: Paul Grubbs, Cornell Tech

[Sandra Wallace via Colloquium]

UNIVERSITY OF CHICAGO
DEPARTMENT OF COMPUTER SCIENCE
PRESENTS



Paul Grubbs
Cornell Tech 
	

Wednesday, November 28, 2018 at 2:00 pm
Crerar 298


Title:  Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks"

Abstract:
As damaging database compromises become more widespread, the question of how to protect sensitive information in databases has received a great deal of interest from academic researchers and practitioners. One popular approach is "encrypted databases": using specialized cryptography to hide the data from the server while supporting queries. To make query evaluation efficient, almost all encrypted databases reveal to the server the access pattern of the queries: whether or not a record in the database matches a query. Prior work has shown via ad-hoc analyses that this leakage can be damaging in very specific settings, but a general framework for understanding security in the presence of access pattern leakage has been elusive.

In this talk, I'll describe some recent progress my coauthors and I have made towards this goal. Our work builds on a very basic insight about access pattern leakage: for each encrypted record, its access pattern can be viewed as a binary classification of the underlying value. This surfaces a useful and natural connection between access pattern leakage and statistical learning theory. I'll explore this connection and show how concepts like Vapnik-Chervonenkis (VC) dimension and epsilon nets can be used both to build new attacks on encrypted databases (generalizing the prior work of Kellaris et al. and Lacharité et al.) and to prove that some information can be hidden even if access patterns are leaked. 

Joint work with Marie-Sarah Lacharité, Brice Minaud, and Kenny Paterson.


https://www.cs.cornell.edu/~paulgrubbs/ <https://www.cs.cornell.edu/~paulgrubbs/>


Host:  David Cash
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20181126/180574ec/attachment-0002.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PastedGraphic-3.pdf
Type: application/pdf
Size: 82855 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20181126/180574ec/attachment-0001.pdf>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20181126/180574ec/attachment-0003.html>