Two-Level Private Information Retrieval

Ruida Zhou, Texas A&M University, Chao Tian, Texas A&M University, Hua Sun, University of North Texas, James S. Plank, EECS Department, University of Tennessee.

IEEE Journal on Selected Areas in Information Theory, 3(2), June, 2022.

Link from the IEEE to the paper.

Abstract

In the conventional robust T-colluding private information retrieval (PIR) system, the user needs to retrieve one of the possible messages while keeping the identity of the requested message private from any T colluding servers. Motivated by the possible heterogeneous privacy requirements for different messages, we consider the (N,T₁ : K₁,T₂ : K₂) two-level PIR system with a total of K₂ messages in the system, where T₁≥T₂ and K₁≤K₂ . Any one of the K₁ messages needs to be retrieved privately against T₁ colluding servers, and any one of the full set of K₂ messages needs to be retrieved privately against T₂ colluding servers. We obtain a lower bound to the capacity by proposing two novel coding schemes, namely the non-uniform successive cancelation scheme and the non-uniform block cancelation scheme. A capacity upper bound is also derived. The gap between the upper bound and the lower bounds is analyzed, and shown to vanish when T₁=T₂ . Lastly, we show that the upper bound is in general not tight by providing a stronger bound for a special setting.

Citation Information

Plain Text:

.article        zts:22:tlp
author          R. Zhou and C. Tian and H. Sun and J. S. Plank
title           Two-Level Private Information Retrieval
journal         IEEE Journal on Selected Areas in Information Theory
month           June
year            2022
volume          3
number          2
url             https://ieeexplore.ieee.org/document/9790846
doi             10.1109/JSAIT.2022.3181216
pages           337-349

Bibtex:

@ARTICLE{zts:22:tlp,
	author = "R. Zhou and C. Tian and H. Sun and J. S. Plank",
	title = "Two-Level Private Information Retrieval",
	journal = "IEEE Journal on Selected Areas in Information Theory",
	month = "June",
	year = "2022",
	volume = "3",
	number = "2",
	url = "https://ieeexplore.ieee.org/document/9790846",
	doi = "10.1109/JSAIT.2022.3181216",
	pages = "337-349"
}