Single-server client preprocessing private information retrieval with tight space-time trade-off
Wang, Zhikun
This item's files can only be accessed by the System Administrators group.
Permalink
https://hdl.handle.net/2142/127489
Description
Title
Single-server client preprocessing private information retrieval with tight space-time trade-off
Author(s)
Wang, Zhikun
Issue Date
2024-12-04
Director of Research (if dissertation) or Advisor (if thesis)
Ren, Ling
Department of Study
Siebel School Comp & Data Sci
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
Private Information Retrieval
Abstract
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
