Practical protocols for private information retrieval

Mughees, Muhammad Haris

Permalink

https://hdl.handle.net/2142/124678 Copy

Description

Title

Practical protocols for private information retrieval

Author(s)

Mughees, Muhammad Haris

Issue Date

2024-04-22

Director of Research (if dissertation) or Advisor (if thesis)

Ren, Ling

Doctoral Committee Chair(s)

Ren, Ling

Committee Member(s)

• Borisov, Nikita
• Gunter, Carl
• Lepoint, Tancrède
• Wu, David

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Privacy, Applied Cryptography, Database

Abstract

The privacy of user queries is a critical problem that affects many cloud-based applications, such as location services, DNS lookups, and online messaging. This thesis studies a cryptographic primitive called Private Information Retrieval (PIR), which hides a client's query from the database server. While PIR is very compelling from a privacy standpoint, current protocols incur a significant performance overhead. In particular, current practical PIR protocols, which leverage somewhat homomorphic encryption (SHE), have high communication overhead due to aggressive noise growth in the underlying homomorphic encryption operations and high server computation due to a linear number of complex homomorphic encryption operations. Two variants of PIR, BatchPIR and Stateful PIR, have been proposed, both aimed at improving the computation when the client has multiple queries. Unfortunately, even the protocols for these variants have several practical limitations. In previous BatchPIR schemes, communication does not get amortized, resulting in high communication overhead, especially when dealing with small entries. Meanwhile, in Stateful PIR, among other challenges, the client must store hints of substantial size, which can be a hurdle for devices with limited storage capacity. This thesis proposes three new practical PIR protocols to overcome these limitations. Our first protocol, OnionPIR, utilizes recent advances in SHE and carefully composes two lattice-based SHE schemes and homomorphic operations to control the noise growth and response size. OnionPIR achieves a response overhead of just 4.2x over the insecure baseline, in contrast to the 100x response overhead of previous protocols. We also presented an updated version of OnionPIR v2, in which response overhead is only 3x. Additionally, server computation is 2x better in this version than in the previous version and the best PIR schemes. We also demonstrate the practicality of OnionPIR by incorporating it into privacy-preserving ad delivery. We have utilized it to design a highly efficient and privacy-oriented ad delivery system, PrivateFetch. This system can deliver ads within a second, even when the ads database includes millions of ads. We then present the BatchPIR protocol, Vectorized BatchPIR, in which computation and communication are amortized, resulting in efficient overall performance for various database configurations. This protocol uses vectorized homomorphic encryption that allows oblivious merging of PIR responses. Our protocol's communication cost is 7.5x to 98.5x better than previous solutions for retrieving 256 entries from a database with one million entries of 256 bytes each. Finally, we design a new stateful PIR protocol, RingPIR, in which the client storage is significantly smaller than the previous schemes. Concretely, to fetch an entry from a database with 32 bytes and 16 million entries, the client storage is only 290 KB, 100 times smaller than the previous protocols. Additionally, the amortized computation is comparable to other stateful protocols and around 79x cheaper than the stateless protocol. Most stateful PIR protocols, including RingPIR, require the client to fetch the hint from the server privately in the offline phase. However, to fetch this hint, all the previous protocols require the server to download an entire database. We, therefore, propose an efficient hint retrieval protocol that uses a technique based on the homomorphic evaluation of copy networks. The proposed approach drastically reduces its response overhead by avoiding downloading the entire database in the offline stage. Specifically, for an entry size of 30 KB, the response size is reduced by 27 to 3,900x.

Graduation Semester

2024-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2024 Muhammad Haris Mughees

Owning Collections