<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div dir="auto" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div dir="auto" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"></div><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><br class=""></div><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div class="" style="orphans: 2; widows: 2;"><div class="" style="margin: 0in 0in 0.0001pt;"><b class=""><font size="4" class="">Paul Grubbs</font></b></div><div class="" style="margin: 0in 0in 0.0001pt;"><span class=""><span class=""><span style="font-size: 14px;" class=""><i class="">Cornell Tech </i></span><br class=""></span></span><div class=""><span class="" style="font-size: 14px;"><i class=""><span class="Apple-tab-span" style="white-space: pre;"> </span></i></span></div></div><div class="" style="margin: 0in 0in 0.0001pt;"><b class=""><font class="" style="font-size: 14px;"><br class=""></font></b></div><div class="" style="margin: 0in 0in 0.0001pt;"><span class="" style="font-size: 14px;"><b class=""><font class="">Wednesday, November 28, 2018 at 2:00 pm<br class="">Crerar 298</font></b><br class=""></span></div></div><div class="" style="orphans: 2; widows: 2;"><span class="" style="font-size: 14px;"><br class=""></span></div><div class=""><br class=""></div><div class=""><div class=""><b class="" style="color: rgb(33, 33, 33); font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px;">Title: </b><font color="#212121" face="Roboto, Helvetica, Arial, sans-serif" class=""><span class="" style="font-size: 14px;">Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks"</span></font></div><div class="" style="color: rgb(33, 33, 33); font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px;"><b class=""><br class=""></b></div><div class="" style="color: rgb(33, 33, 33); font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px;"><b class="">Abstract:</b></div><div class=""><font class=""><span class=""><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><div class=""><font color="#222222" class=""><span class=""><span style="font-size: 14px;" class="">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.<br class=""><br class="">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. <br class=""><br class="">Joint work with Marie-Sarah Lacharité, Brice Minaud, and Kenny Paterson.</span></span></font></div><div class=""><font color="#222222" class=""><span class=""><span style="font-size: 14px;" class=""><br class=""></span><br class=""></span></font></div><div class=""><a href="https://www.cs.cornell.edu/~paulgrubbs/" style="font-size: 14px;" class="">https://www.cs.cornell.edu/~paulgrubbs/</a></div><div class=""><font color="#222222" class=""><span class=""><br class=""></span></font></div></div></span></font></div><div class=""><b class="" style="color: rgb(33, 33, 33); font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px;"><br class=""></b></div><div class=""><b class="" style="color: rgb(33, 33, 33); font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px;">Host: David Cash</b></div></div></div></div></div></div></div></div></body></html>