{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/124678"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/124678","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Practical protocols for private information retrieval","abstract":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2026-05-01","abstract_html":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2026-05-01","abstract_has_math":false,"creators":["Mughees, Muhammad Haris"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Ren, Ling","Borisov, Nikita","Gunter, Carl","Lepoint, Tancrède","Wu, David"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-05","date_published":"2024-05","updated_at":"2026-07-22T22:25:02Z","subjects":["Privacy","Applied Cryptography","Database"],"languages":["en","eng"],"rights":["Copyright 2024 Muhammad Haris Mughees"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/124678","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Ren, Ling","Borisov, Nikita","Gunter, Carl","Lepoint, Tancrède","Wu, David"]},{"key":"dc:creator","label":"Author","values":["Mughees, Muhammad Haris"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024-05","2024-04-22"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Privacy","Applied Cryptography","Database"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2024 Muhammad Haris Mughees"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/124678"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2026-05-01","The student, Muhammad Haris Mughees, accepted the attached license on 2024-04-21 at 14:51.","The student, Muhammad Haris Mughees, submitted this Dissertation for approval on 2024-04-21 at 14:57.","This Dissertation was approved for publication on 2024-04-22 at 11:09.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20522 on 2024-09-16 at 00:49:37","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Practical protocols for private information retrieval"]}]}],"canonical_facts":{"dc:contributor":["Ren, Ling","Borisov, Nikita","Gunter, Carl","Lepoint, Tancrède","Wu, David"],"dc:creator":["Mughees, Muhammad Haris"],"dc:date":["2024-05","2024-04-22"],"dc:description":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2026-05-01","The student, Muhammad Haris Mughees, accepted the attached license on 2024-04-21 at 14:51.","The student, Muhammad Haris Mughees, submitted this Dissertation for approval on 2024-04-21 at 14:57.","This Dissertation was approved for publication on 2024-04-22 at 11:09.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20522 on 2024-09-16 at 00:49:37","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/124678"],"dc:language":["en","eng"],"dc:rights":["Copyright 2024 Muhammad Haris Mughees"],"dc:subject":["Privacy","Applied Cryptography","Database"],"dc:title":["Practical protocols for private information retrieval"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:02Z"}