[Colloquium] Reminder - Francesca Falzon Dissertation Defense/Apr 28, 2023

[Megan Woodward]

This is an announcement of Francesca Falzon's Dissertation Defense.
===============================================
Candidate: Francesca Falzon

Date: Friday, April 28, 2023

Time: 10 am CST

Remote Location:  https://uchicago.zoom.us/j/99129159192?pwd=MkRIcGFmbnFFYUpDTFBsbzFudmtRUT09<https://urldefense.com/v3/__https://uchicago.zoom.us/j/99129159192?pwd=MkRIcGFmbnFFYUpDTFBsbzFudmtRUT09__;!!BpyFHLRN4TMTrA!8cIxyivZyk9rcEfIOZq7PCGPoKRQ6SYlq79CNm2J0sR2rCBHpq2XTlzULngf8iGylkWzaImaf7Uf3Wr59nmc_ijfWgse8mJbhYL2$>


Title: A Combinatorial Approach to Leakage Abuse Attacks and Their Mitigation

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.
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.

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.

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.

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.

Advisors: Ben Zhao & Roberto Tamassia

Committee Members: Roberto Tamassia, Ben Zhao, Kenneth G. Paterson, Aloni Cohen





-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230428/cdbfb776/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: FFalzon-Thesis.pdf
Type: application/pdf
Size: 8277323 bytes
Desc: FFalzon-Thesis.pdf
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230428/cdbfb776/attachment-0001.pdf>