<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
</head>
<body>
<div class="" style="word-wrap:break-word"><span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">This is an announcement of Francesca Falzon's Dissertation Defense.</span><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">===============================================</span><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">Candidate: Francesca Falzon</span><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">Date: Friday, April 28, 2023</span><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">Time: 10 am CST</span><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">Remote Location: </span><a href="https://urldefense.com/v3/__https://uchicago.zoom.us/j/99129159192?pwd=MkRIcGFmbnFFYUpDTFBsbzFudmtRUT09__;!!BpyFHLRN4TMTrA!8cIxyivZyk9rcEfIOZq7PCGPoKRQ6SYlq79CNm2J0sR2rCBHpq2XTlzULngf8iGylkWzaImaf7Uf3Wr59nmc_ijfWgse8mJbhYL2$" target="_blank" rel="noopener noreferrer" class="" style="border:0px; font-size:14.666666984558105px; font-stretch:inherit; line-height:inherit; margin:0px; padding:0px; vertical-align:baseline">https://uchicago.zoom.us/j/99129159192?pwd=MkRIcGFmbnFFYUpDTFBsbzFudmtRUT09</a><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">Title: A Combinatorial Approach to Leakage Abuse Attacks and Their Mitigation</span><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">Abstract: With the rise of remote cloud services and the consequent rise in data breaches, there is an increased need for the secure outsourcing of
data. The problem of enabling query processing over encrypted data without decryption is a challenging one, and approaches ranging from software to hardware have been proposed.</span><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">In this work, we take a closer look at a class of solutions that are efficient and deployable in the near-term future and that employ the use of light
weight symmetric key primitives. In exchange for this added efficiency, these schemes leak certain information about the underlying data and queries. We explore the limitations of what a passive server-side adversary can learn from this information leakage
and present practical constructions that minimize leakage while supporting complex queries.</span><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">In particular, we investigate the security of encrypted databases that support two types of expressive queries: range queries on multi-attribute data
and shortest path queries on graph-structured data. The former is a common database query on relational data that requests all records whose attribute values lie within given query intervals. The latter is a fundamental graph query that returns the shortest
path in a graph between two nodes, and has applications to the analysis of routing networks, metabolic networks, and social networks. Multi-attribute data and graph-structured data are ubiquitous in our increasingly data-driven world, and understanding the
security of how to encrypt them while also supporting expressive queries will help move us towards practical deployment.</span><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">In the first part of this work, we present the first attacks on schemes that support range queries over multi-attribute (or multi-dimensional) data.
We describe the information theoretic limitation of reconstruction attacks in two settings and show that, in both cases, there can be an exponential number of distinct databases that produce equivalent leakage. We present a full database reconstruction attack
that reconstructs the database when all queries are observed. We then relax these assumptions, and present an order reconstruction attack and an approximate database reconstruction attack that require only a strict subset of the possible range queries to succeed.</span><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">In the second part of this work, we shift our focus to schemes that support shortest path queries on graph-structured data. We initiate our study by
describing an attack that recovers the plaintext queries issued by the client on a graph encryption scheme, which we call the GKT scheme (Ghosh et al. AsiaCCS 2021). We then present a modified version of the GKT scheme with reduced leakage in exchange for
a 2x increase in bandwidth overhead and a logarithmic increase in storage overhead. Our scheme uses data-structure techniques to decompose the graph into edge-disjoint paths. These paths are then stored in a multimap and encrypted using a standard encrypted
multimap scheme. We support our scheme with a detailed cryptanalysis and explain why this new approach mitigates our previous attack.</span><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">Advisors: Ben Zhao & Roberto Tamassia</span><br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<br aria-hidden="true" class="" style="color:rgb(36,36,36); font-size:14.666666984558105px">
<span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)">Committee Members: Roberto Tamassia, Ben Zhao, Kenneth G. Paterson, Aloni Cohen</span>
<div class=""><span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)"><br class="">
</span></div>
<div class=""><span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)"><br class="">
</span></div>
<div class=""></div>
</div>
<div class="" style="word-wrap:break-word">
<div class=""></div>
<div class=""><span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)"><br class="">
</span></div>
<div class=""><span class="" style="color:rgb(36,36,36); font-size:14.666666984558105px; background-color:rgb(255,255,255)"><br class="">
</span></div>
</div>
</body>
</html>