More Like this

1. On Single Server Private Information Retrieval With Private Coded Side Information

   https://doi.org/10.1109/TIT.2023.3253078  

   Lu, Yuxiang; Jafar, Syed A. (May 2023, IEEE Transactions on Information Theory)

   Matthieu Bloch (Ed.)

   Motivated by an open problem and a conjecture, this work studies the problem of single server private information retrieval with private coded side information (PIR-PCSI) that was recently introduced by Heidarzadeh et al. The goal of PIR-PCSI is to allow a user to efficiently retrieve a desired message Wθ, which is one of K independent messages that are stored at a server, while utilizing private side information of a linear combination of a uniformly chosen size-M subset (S ⊂ [K]) of messages. The settings PIR-PCSI-I and PIR-PCSI-II correspond to the constraints that θ is generated uniformly from [K]\S, and S, respectively. In each case, (θ, S) must be kept private from the server. The capacity is defined as the supremum over message and field sizes, of achievable rates (number of bits of desired message retrieved per bit of download) and is characterized by Heidarzadeh et al. for PIR-PCSI-I in general, and for PIR- PCSI-II for M > (K + 1)/2 as (K − M + 1)−1. For 2 ≤ M ≤ (K + 1)/2 the capacity of PIR-PCSI-II remains open, and it is conjectured that even in this case the capacity is (K − M + 1)−1. We show the capacity of PIR-PCSI-II is equal to 2/K for 2 ≤ M ≤ K+1, which is strictly larger 2 than the conjectured value, and does not depend on M within this parameter regime. Remarkably, half the side-information is found to be redundant. We also characterize the infimum capacity (infimum over fields instead of supremum), and the capacity with private coefficients. The results are generalized to PIR-PCSI-I (θ ∈ [K] \ S) and PIR-PCSI (θ ∈ [K]) settings. 

   more » « less
2. Faster FHE-Based Single-Server Private Information Retrieval

   https://doi.org/10.1145/3658644.3690233  

   Luo, Ming; Liu, Feng-Hao; Wang, Han (December 2024, ACM)
3. Single-Server Multi-Message Individually-Private Information Retrieval with Side Information

   https://doi.org/10.1109/ISIT.2019.8849283  

   Heidarzadeh, Anoosheh; Kadhe, Swanand; El Rouayheb, Salim; Sprintson, Alex (July 2019, 2019 IEEE International Symposium on Information Theory (ISIT))
4. Private Computation with Side Information: The Single-Server Case

   https://doi.org/10.1109/ISIT.2019.8849287  

   Heidarzadeh, Anoosheh; Sprintson, Alex (July 2019, 2019 IEEE International Symposium on Information Theory (ISIT))
5. Single-Server Private Information Retrieval with Sublinear Amortized Time

   https://doi.org/10.1007/978-3-031-07085-3_1  

   Corrigan-Gibbs, H. (May 2022, Lecture notes in computer science)

   Dunkelman, D.; Dziembowski, S. (Ed.)

   We construct new private-information-retrieval protocols in the single-server setting. Our schemes allow a client to privately fetch a sequence of database records from a server, while the server answers each query in average time sublinear in the database size. Specifically, we introduce the first single-server private-information-retrieval schemes that have sublinear amortized server time, require sublinear additional storage, and allow the client to make her queries adaptively. Our protocols rely only on standard cryptographic assumptions (decision Diffie-Hellman, quadratic residuosity, learning with errors, etc.). They work by having the client first fetch a small “hint” about the database contents from the server. Generating this hint requires server time linear in the database size. Thereafter, the client can use the hint to make a bounded number of adaptive queries to the server, which the server answers in sublinear time—yielding sublinear amortized cost. Finally, we give lower bounds proving that our most efficient scheme is optimal with respect to the trade-off it achieves between server online time and client storage. 

   more » « less