2-Server PIR with Sub-Polynomial Communication

DOI10.1145/2746539.2746546zbMath1321.68253arXiv1407.6692OpenAlexW2033498419MaRDI QIDQ2941552

Sivakanth Gopi, Zeev Dvir

Publication date: 21 August 2015

Published in: Journal of the ACM, Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.6692

zbMATH Keywords

locally decodable codesprivate information retrieval

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Decoding (94B35) Communication theory (94A05)

Related Items

Measuring, simulating and exploiting the head concavity phenomenon in BKZ ⋮ Puncturable pseudorandom sets and private information retrieval with near-optimal online bandwidth and time ⋮ Towards breaking the exponential barrier for general secret sharing ⋮ Single-server private information retrieval with sublinear amortized time ⋮ Optimal single-server private information retrieval ⋮ Lower bounds for (batch) PIR with private preprocessing ⋮ A survey on single server private information retrieval in a coding theory perspective ⋮ Unnamed Item ⋮ On the optimal communication complexity of error-correcting multi-server PIR ⋮ Oblivious-transfer complexity of noisy coin-toss via secure zero communication reductions ⋮ \textsf{TreePIR}: sublinear-time and polylog-bandwidth private information retrieval from DDH ⋮ Optimal linear multiparty conditional disclosure of secrets protocols ⋮ Foundations of Homomorphic Secret Sharing ⋮ Improved user-private information retrieval via finite geometry ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Asymptotically Tight Bounds for Composing ORAM with PIR ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Private information retrieval with sublinear online time ⋮ Outlaw distributions and locally decodable codes ⋮ A general private information retrieval scheme for MDS coded databases with colluding servers ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ Some Open Problems in Information-Theoretic Cryptography ⋮ Reed-Muller Codes

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming