Bounds on the Capacity of Private Information Retrieval Over Graphs

被引：4

作者：

Sadeh, Bar ^{[1
]}

Gu, Yujie ^{[2
]}

Tamo, Itzhak

机构：

[1] Tel Aviv Univ, Dept Elect Engn & Syst, IL-39040 Tel Aviv, Israel

[2] Kyushu Univ, Fac Informat Sci & Elect Engn, Fukuoka 8190395, Japan

来源：

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY | 2023年 / 18卷

基金：

日本学术振兴会; 以色列科学基金会; 欧洲研究理事会;

关键词：

Private information retrieval (PIR); graph-based replication system; edge-coloring; capacity; DISTRIBUTED STORAGE; CODED DATABASES;

D O I：

10.1109/TIFS.2022.3220034

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the private information retrieval (PIR) problem, a user wants to retrieve a file from a database without revealing any information about the desired file's identity to the servers that store the database. In this paper, we study the PIR capacity of a graph-based replication system, in which each file is stored on two distinct servers according to an underlying graph. This paper aims to provide upper and lower bounds to the PIR capacity of graphs via various graph properties. In particular, we provide several upper bounds on the PIR capacity that apply to all graphs. We further improve the bounds for specific graph families (which turn out to be tight in certain cases) by utilizing the underlying graph structure. For the lower bounds, we establish optimal rate PIR schemes for star graphs via edge-coloring techniques. Lastly, we provide an improved PIR scheme for complete graphs, implying an improved general lower bound on all graphs' PIR capacity.

引用

页码：261 / 273

页数：13

共 40 条

[1]

Ambainis A, 1997, LECT NOTES COMPUT SC, V1256, P401

[2] The Capacity of Private Information Retrieval From Uncoded Storage Constrained Databases [J].

Attia, Mohamed Adel ;

Kumar, Deepak ;

Tandon, Ravi .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (11) :6617-6634

[3]

Banawan K, 2019, IEEE INT SYMP INFO, P1272, DOI [10.1109/ISIT.2019.8849399, 10.1109/isit.2019.8849399]

[4] The Capacity of Private Information Retrieval From Coded Databases [J].

Banawan, Karim ;

Ulukus, Sennur .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2018, 64 (03) :1945-1956

[5]

Baranyai Z., 1975, C MATH SOC J NOS BOL, V10, P91

[6]

Brouwer A E., 1979, Packing and Covering in Combinatorics, P39

[7]

Chan TH, 2015, IEEE INT SYMP INFO, P2842, DOI 10.1109/ISIT.2015.7282975

[8]

Chor B, 1995, AN S FDN CO, P41, DOI 10.1109/SFCS.1995.492461

[9] Private information retrieval [J].

Chor, B ;

Goldreich, O ;

Kushilevitz, E ;

Sudan, M .

JOURNAL OF THE ACM, 1998, 45 (06) :965-982

[10]

docs.datastax, AP CASS 2 1 DSE DAT

← 1 2 3 4 →