[Colloquium] Alex Hoover Dissertation Defense/Apr 15, 2024

[meganwoodward at uchicago.edu]

This is an announcement of Alex Hoover's Dissertation Defense.
===============================================
Candidate: Alex Hoover

Date: Monday, April 15, 2024

Time: 10:30 am CT

Remote Location:  https://uchicago.zoom.us/j/4767905734?pwd=a3lZUXZiMHAzc29QYncvcWlSU01sUT09

Location: JCL 346

Title: On the Limits of Efficiency and Privacy for Outsourced Computation

Abstract: Private Information Retrieval (PIR) is a cryptographic primitive that allows a client to query for some element of a public database, held by a server, without revealing the element that the client is interested in. Recent developments in PIR have used client-side preprocessing to speed up online query times. In this model, a client can run offline to compute a hint which it later uses to issue online queries. Unfortunately, all proposed solutions in this model before this work suffer from two significant drawbacks: (1) updating an entry in the database requires some inefficient computation and (2) a client's query time is linear in their hint size.

In this work, we overcome both of these obstacles by proposing Plinko, a new PIR scheme in the client-side preprocessing model. As part of our construction, we provide a new primitive called an invertible pseudorandom function, which allows someone with the secret key to find the pre-image of some output efficiently. This primitive allows us to generically upgrade two previously proposed schemes to both: (1) update entries with nearly-constant time and communication and (2) avoid clients' linear pass through their hints, improving the asymptotic runtime for clients with large storage.

This talk focuses on the third and final chapter of my dissertation. However, I briefly discuss the how the other chapters in my dissertation contribute to the exploration of efficiency and privacy in outsourced computation.

Advisors: David Cash

Committee Members: David Cash, Aloni Cohen, and Raul Castro Fernandez