A tight lower bound for restricted pir protocols

被引：16

作者：

Beigel, R

Fortnow, L

Gasarch, W

机构：

[1] Temple Univ, Dept Comp & Informat Sci, Philadelphia, PA 19122 USA

[2] Univ Chicago, Dept Comp Sci, Chicago, IL 60637 USA

[3] Univ Maryland, Dept Comp Sci, College Pk, MD 20742 USA

[4] Univ Maryland, Inst Adv Comp Studies, College Pk, MD 20742 USA

来源：

COMPUTATIONAL COMPLEXITY | 2006年 / 15卷 / 01期

关键词：

private information retrieval; lower bounds; privacy;

D O I：

10.1007/s00037-006-0208-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that any 1-round 2-server Private Information Retrieval Protocol where the answers are one bit long must ask questions that are at least n-2 bits long, which is nearly equal to the known n-1 upper bound. This improves upon the approximately 0.25n lower bound of Kerenidis and deWolf while avoiding their use of quantum techniques.

引用

页码：82 / 91

页数：10

共 13 条

[1]

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

[2]

Beimel A, 2002, ANN IEEE SYMP FOUND, P261, DOI 10.1109/SFCS.2002.1181949

[3]

Cachin C, 1999, LECT NOTES COMPUT SC, V1592, P402

[4] Private information retrieval [J].