{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/127489"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/127489","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Single-server client preprocessing private information retrieval with tight space-time trade-off","abstract":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2026-12-01","abstract_html":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2026-12-01","abstract_has_math":false,"creators":["Wang, Zhikun"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Ren, Ling"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-12-04","date_published":"2024-12-04","updated_at":"2026-07-22T22:25:04Z","subjects":["Private Information Retrieval"],"languages":["en","eng"],"rights":["Copyright 2024 Zhikun Wang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/127489","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Ren, Ling"]},{"key":"dc:creator","label":"Author","values":["Wang, Zhikun"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024-12-04","2024-12"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"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":["Private Information Retrieval"]}]},{"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 Zhikun Wang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/127489"]}]},{"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-12-01","The student, Zhikun Wang, accepted the attached license on 2024-12-03 at 16:32.","The student, Zhikun Wang, submitted this Thesis for approval on 2024-12-03 at 16:44.","This Thesis was approved for publication on 2024-12-04 at 20:47.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21479 on 2025-03-28 at 14:55:37","Private Information Retrieval (PIR) studies the problem of retrieving an entry from a public database without revealing the index of the entry to the server. This thesis partly solves the open problem of tight trade-off of client storage and server time in the client preprocessing setting of PIR. In the client preprocessing setting of PIR, the client is allowed to store some hints generated from the database in a preprocessing phase and use the hints to assist online queries. We construct a new single-server client preprocessing PIR scheme. For a database with n entries of size w, our protocol uses S=O((n/T) * (log n + w)) bits of client storage and T amortized server probes over n/T queries, where T is a tunable online time parameter. Our scheme matches (up to constant factors) a ST = Omega(nw) lower bound generalized from a recent work by Yeo and a communication barrier generalized from Ishai, Shi, and Wichs. From a technical standpoint, we present a novel organization of hints where each PIR query consumes a hint, and entries in the consumed hint are relocated to other hints. We then present a new data structure to track the hint relocations and use small-domain pseudorandom permutations to make the hint storage sublinear while maintaining efficient lookups in the hints."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Single-server client preprocessing private information retrieval with tight space-time trade-off"]}]}],"canonical_facts":{"dc:contributor":["Ren, Ling"],"dc:creator":["Wang, Zhikun"],"dc:date":["2024-12-04","2024-12"],"dc:description":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2026-12-01","The student, Zhikun Wang, accepted the attached license on 2024-12-03 at 16:32.","The student, Zhikun Wang, submitted this Thesis for approval on 2024-12-03 at 16:44.","This Thesis was approved for publication on 2024-12-04 at 20:47.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21479 on 2025-03-28 at 14:55:37","Private Information Retrieval (PIR) studies the problem of retrieving an entry from a public database without revealing the index of the entry to the server. This thesis partly solves the open problem of tight trade-off of client storage and server time in the client preprocessing setting of PIR. In the client preprocessing setting of PIR, the client is allowed to store some hints generated from the database in a preprocessing phase and use the hints to assist online queries. We construct a new single-server client preprocessing PIR scheme. For a database with n entries of size w, our protocol uses S=O((n/T) * (log n + w)) bits of client storage and T amortized server probes over n/T queries, where T is a tunable online time parameter. Our scheme matches (up to constant factors) a ST = Omega(nw) lower bound generalized from a recent work by Yeo and a communication barrier generalized from Ishai, Shi, and Wichs. From a technical standpoint, we present a novel organization of hints where each PIR query consumes a hint, and entries in the consumed hint are relocated to other hints. We then present a new data structure to track the hint relocations and use small-domain pseudorandom permutations to make the hint storage sublinear while maintaining efficient lookups in the hints."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/127489"],"dc:language":["en","eng"],"dc:rights":["Copyright 2024 Zhikun Wang"],"dc:subject":["Private Information Retrieval"],"dc:title":["Single-server client preprocessing private information retrieval with tight space-time trade-off"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:04Z"}