Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

On the Security of Doubly Efficient PIR.

Elette Boyle, Justin Holmgren, Fermi Ma, Mor Weiss

Published Jan 1, 2021• 1 citation
OpenAlex

Related papers

Communication-Computation Trade-offs in PIR.

Asra Ali, Tancrède Lepoint, Sarvar Patel +4 more

USENIX Security Symposium•Jan 1, 2019•49 citations

A tight lower bound for restricted pir protocols

Richard Beigel, Lance Fortnow, William I. Gasarch

Computational Complexity•Apr 25, 2006•24 citations

Lower-Bounds on Public-Key Operations in PIR

Jesko Dujmovic, Mohammad Hajiabadi

Lecture notes in computer science•Jan 1, 2024•3 citations

Simplified PIR and CDS Protocols and Improved Linear Secret-Sharing Schemes

Bar Alon, Amos Beimel, Or Lasri

Lecture notes in computer science•Dec 1, 2025•4 citations

On Quantum Advantage in Information Theoretic Single-Server PIR

Dorit Aharonov, Zvika Brakerski, Kai-Min Chung +3 more

Lecture notes in computer science•Jan 1, 2019•16 citations

A study of secure database access and general two-party computation

Tal Malkin, Shafi Goldwasser

In this thesis, we study two fundamental areas of secure computation over a network.First, we study general two-party secure computation, where two mutually distrustful parties are trying to compute an arbitrary function of their inputs, without revealing any extra information (even if one of them is malicious).We prove that, if any nontrivial function can be so computed, then so can every other function.That is, every non-trivial function is complete for two-party secure computation.Consequently, the complexity assumptions sufficient and/or necessary for securely computing f are the same for every non-trivial function f.Next, we study the concrete problem of secure database access, where the privacy of both the database and the user is to be protected from each other and from all other participating or eavesdropping parties.We are interested in practical and theoretical aspects of this problem, addressing issues of efficiency, security, and complexity.More specifically, we start from the model of private information retrieval (PIR), where users are trying to retrieve information from a database while keeping their queries private from the database owner.We then explore the following directions: * We study the necessary assumptions for single server PIR with low communication.We prove that oblivious transfer is necessary, implying that PIR is a complete primitive for secure computation, and that computational SPIR protocols (defined below) can be efficiently constructed from PIR protocols.* We introduce the model of SPIR, where the privacy of the data, as well as the user, is guaranteed.We show how to efficiently transform PIR protocols into SPIR protocols, for both the information-theoretic and computational settings. "We introduce the random server model for PIR, and show how to use it to achieve information theoretic solutions in which the database need not give away its data to be replicated, and with minimal on-line computation for the database.

•Jan 1, 2000•7 citations
In this thesis, we study two fundamental areas of secure computation over a network.First, we study general two-party secure computation, where two mutually distrustful parties are trying to compute an arbitrary function of their inputs, without revealing any extra information (even if one of them is malicious).We prove that, if any nontrivial function can be so computed, then so can every other function.That is, every non-trivial function is complete for two-party secure computation.Consequently, the complexity assumptions sufficient and/or necessary for securely computing f are the same for every non-trivial function f.Next, we study the concrete problem of secure database access, where the privacy of both the database and the user is to be protected from each other and from all other participating or eavesdropping parties.We are interested in practical and theoretical aspects of this problem, addressing issues of efficiency, security, and complexity.More specifically, we start from the model of private information retrieval (PIR), where users are trying to retrieve information from a database while keeping their queries private from the database owner.We then explore the following directions: * We study the necessary assumptions for single server PIR with low communication.We prove that oblivious transfer is necessary, implying that PIR is a complete primitive for secure computation, and that computational SPIR protocols (defined below) can be efficiently constructed from PIR protocols.* We introduce the model of SPIR, where the privacy of the data, as well as the user, is guaranteed.We show how to efficiently transform PIR protocols into SPIR protocols, for both the information-theoretic and computational settings. "We introduce the random server model for PIR, and show how to use it to achieve information theoretic solutions in which the database need not give away its data to be replicated, and with minimal on-line computation for the database.