Upper bound on the communication complexity of private information retrieval

DOI10.1007/3-540-63165-8_196zbMath1401.68065OpenAlexW1832668820MaRDI QIDQ4571971

Andris Ambainis

Publication date: 4 July 2018

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63165-8_196

Mathematics Subject Classification ID

Database theory (68P15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60) Information storage and retrieval of data (68P20)

Related Items

Quantum symmetrically-private information retrieval ⋮ Single-server private information retrieval with sublinear amortized time ⋮ On locally decodable codes, self-correctable codes, and \(t\)-private PIR ⋮ Enhancing user privacy in SARG04-based private database query protocols ⋮ Lower bounds for (batch) PIR with private preprocessing ⋮ On the optimal communication complexity of error-correcting multi-server PIR ⋮ Query-efficient locally decodable codes of subexponential length ⋮ Communication-efficient distributed oblivious transfer ⋮ Lower bounds for adaptive locally decodable codes ⋮ General constructions for information-theoretic private information retrieval ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Exponential lower bound for 2-query locally decodable codes via a quantum argument ⋮ Security improvements of several basic quantum private query protocols with \(O(\log N)\) communication complexity ⋮ Verifiable single-server private information retrieval from LWE with binary errors ⋮ Private information retrieval with sublinear online time ⋮ Short Locally Testable Codes and Proofs ⋮ Protecting data privacy in private information retrieval schemes ⋮ An optimal lower bound for 2-query locally decodable linear codes

Cites Work

• On hiding information from an oracle
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Upper bounds on multiparty communication complexity of shifts
• Simultaneous messages vs. communication
• Modified ranks of tensors and the size of circuits
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item