A survey of single-database private information retrieval: techniques and applications
---
paper_title: Searchable symmetric encryption: Improved definitions and efficient constructions

paper_content:

Searchable symmetric encryption SSE allows a party to outsource the storage of his data to another party in a private manner, while maintaining the ability to selectively search over it. This problem has been the focus of active research and several security definitions and constructions have been proposed. In this paper we begin by reviewing existing notions of security and propose new and stronger security definitions. We then present two constructions that we show secure under our new definitions. Interestingly, in addition to satisfying stronger security guarantees, our constructions are more efficient than all previous constructions.Further, prior work on SSE only considered the setting where only the owner of the data is capable of submitting search queries. We consider the natural extension where an arbitrary group of parties other than the owner can submit search queries. We formally define SSE in this multi-user setting, and present an efficient construction.
---
paper_title: Software protection and simulation on oblivious RAMs

paper_content:

Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the theoretical treatment it deserves. In this paper, we provide theoretical treatment of software protection. We reduce the problem of software protection to the problem of efficient simulation on oblivious RAM. A machine is oblivious if thhe sequence in which it accesses memory locations is equivalent for any two inputs with the same running time. For example, an oblivious Turing Machine is one for which the movement of the heads on the tapes is identical for each computation. (Thus, the movement is independent of the actual input.) What is the slowdown in the running time of a machine, if it is required to be oblivious? In 1979, Pippenger and Fischer showed how a two-tape oblivious Turing Machine can simulate, on-line, a one-tape Turing Machine, with a logarithmic slowdown in the running time. We show an analogous result for the random-access machine (RAM) model of computation. In particular, we show how to do an on-line simulation of an arbitrary RAM by a probabilistic oblivious RAM with a polylogaithmic slowdown in the running time. On the other hand, we show that a logarithmic slowdown is a lower bound.
---
paper_title: Computationally private information retrieval with polylogarithmic communication

paper_content:

We present a single-database computationally private information retrieval scheme with polylogarithmic communication complexity. Our construction is based on a new, but reasonable intractability assumption, which we call the φ-Hiding Assumption (φHA): essentially the difficulty of deciding whether a small prime divides φ(m), where m is a composite integer of unknown factorization.
---
paper_title: Replication is not needed: single database, computationally-private information retrieval

paper_content:

We establish the following, quite unexpected, result: replication of data for the computational private information retrieval problem is not necessary. More specifically, based on the quadratic residuosity assumption, we present a single database, computationally private information retrieval scheme with O(n/sup /spl epsiv//) communication complexity for any /spl epsiv/>0.
---
paper_title: Single-Database Private Information Retrieval with Constant Communication Rate

paper_content:

We present a single-database private information retrieval (PIR) scheme with communication complexity ${\mathcal O}(k+d)$, where k ≥ log n is a security parameter that depends on the database size n and d is the bit-length of the retrieved database block. This communication complexity is better asymptotically than previous single-database PIR schemes. The scheme also gives improved performance for practical parameter settings whether the user is retrieving a single bit or very large blocks. For large blocks, our scheme achieves a constant “rate” (e.g., 0.2), even when the user-side communication is very low (e.g., two 1024-bit numbers). Our scheme and security analysis is presented using general groups with hidden smooth subgroups; the scheme can be instantiated using composite moduli, in which case the security of our scheme is based on a simple variant of the “Φ-hiding” assumption by Cachin, Micali and Stadler [2].
---
paper_title: Private information retrieval

paper_content:

We describe schemes that enable a user to access k replicated copies of a database (k/spl ges/2) and privately retrieve information stored in the database. This means that each individual database gets no information on the identity of the item retrieved by the user. For a single database, achieving this type of privacy requires communicating the whole database, or n bits (where n is the number of bits in the database). Our schemes use the replication to gain substantial saving. In particular, we have: A two database scheme with communication complexity of O(n/sup 1/3/). A scheme for a constant number, k, of databases with communication complexity O(n/sup 1/k/). A scheme for 1/3 log/sub 2/ n databases with polylogarithmic (in n) communication complexity.
---
paper_title: A Generalisation, a Simplification and some Applications of Paillier’s Probabilistic Public-Key System

paper_content:

We propose a generalisation of Paillier's probabilistic public key system, in which the expansion factor is reduced and which allows to adjust the block length of the scheme even after the public key has been fixed, without losing the homomorphic property. We show that the generalisation is as secure as Paillier's original system. We construct a threshold variant of the generalised scheme as well as zero-knowledge protocols to show that a given ciphertext encrypts one of a set of given plaintexts, and protocols to verify multiplicative relations on plaintexts. We then show how these building blocks can be used for applying the scheme to efficient electronic voting. This reduces dramatically the work needed to compute the final result of an election, compared to the previously best known schemes. We show how the basic scheme for a yes/no vote can be easily adapted to casting a vote for up to t out of L candidates. The same basic building blocks can also be adapted to provide receipt-free elections, under appropriate physical assumptions. The scheme for 1 out of L elections can be optimised such that for a certain range of parameter values, a ballot has size only O(log L) bits.
---
paper_title: An oblivious transfer protocol with log-squared communication

paper_content:

We propose a one-round 1-out-of-n computationally-private information retrieval protocol for l-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computation and communication Θ(klog2n+llogn), where k is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private 1-out-of-n oblivious-transfer protocol for l-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model.
---
paper_title: Single Database Private Information Retrieval with Logarithmic Communication

paper_content:

We study the problem of single database private information retrieval, and present a solution with only logarithmic server-side communication complexity and a solution with only logarithmic user-side communication complexity. Previously the best result could only achieve polylogarithmic communication on each side, and was based on certain less well-studied assumptions in number theory [6]. On the contrary, our schemes are based on Paillier’s cryptosystem [16], which along with its variants have drawn extensive studies in recent cryptographic researches [3, 4, 8, 9], and have many important applications [7, 8].
---
paper_title: One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval

paper_content:

We show that general one-way trapdoor permutations are sufficient to privately retrieve an entry from a database of size n with total communication complexity strictly less than n. More specifically, we present a protocol in which the user sends O(K2) bits and the server sends n - cn/K bits (for any constant c), where K is the security parameter of the trapdoor permutations. Thus, for sufficiently large databases (e.g., when K = nƐ for some small Ɛ) our construction breaks the information-theoretic lower-bound (of at least n bits). This demonstrates the feasibility of basing single-server private information retrieval on general complexity assumptions. ::: ::: An important implication of our result is that we can implement a 1-out-of- n Oblivious Transfer protocol with communication complexity strictly less than n based on any one-way trapdoor permutation.
---
paper_title: Batch codes and their applications

paper_content:

A batch code encodes a string x into an m-tuple of strings, called buckets, such that each batch of k bits from x can be decoded by reading at most one (more generally, t) bits from each bucket. Batch codes can be viewed as relaxing several combinatorial objects, including expanders and locally decodable codes. We initiate the study of these codes by presenting some constructions, connections with other problems, and lower bounds. We also demonstrate the usefulness of batch codes by presenting two types of applications: trading maximal load for storage in certain load-balancing scenarios, and amortizing the computational cost of private information retrieval (PIR) and related cryptographic protocols.
---
paper_title: Replication is not needed: single database, computationally-private information retrieval

paper_content:

We establish the following, quite unexpected, result: replication of data for the computational private information retrieval problem is not necessary. More specifically, based on the quadratic residuosity assumption, we present a single database, computationally private information retrieval scheme with O(n/sup /spl epsiv//) communication complexity for any /spl epsiv/>0.
---
paper_title: Single Database Private Information Retrieval Implies Oblivious Transfer

paper_content:

A Single-Database Private Information Retrieval (PIR) is a protocol that allows a user to privately retrieve from a database an entry with as small as possible communication complexity. We call a PIR protocol non-trivial if its total communication is strictly less than the size of the database. Non-trivial PIR is an important cryptographic primitive with many applications. Thus, understanding which assumptions are necessary for implementing such a primitive is an important task, although (so far) not a well-understood one. In this paper we show that any non-trivial PIR implies Oblivious Transfer, a far better understood primitive. Our result not only significantly clarifies our understanding of any non-trivial PIR protocol, but also yields the following consequences: - Any non-trivial PIR is complete for all two-party and multiparty secure computations. - There exists a communication-efficient reduction from any PIR protocol to a 1-out-of-n Oblivious Transfer protocol (also called SPIR). - There is strong evidence that the assumption of the existence of a one-way function is necessary but not sufficient for any non-trivial PIR protocol.
---
paper_title: One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval

paper_content:

We show that general one-way trapdoor permutations are sufficient to privately retrieve an entry from a database of size n with total communication complexity strictly less than n. More specifically, we present a protocol in which the user sends O(K2) bits and the server sends n - cn/K bits (for any constant c), where K is the security parameter of the trapdoor permutations. Thus, for sufficiently large databases (e.g., when K = nƐ for some small Ɛ) our construction breaks the information-theoretic lower-bound (of at least n bits). This demonstrates the feasibility of basing single-server private information retrieval on general complexity assumptions. ::: ::: An important implication of our result is that we can implement a 1-out-of- n Oblivious Transfer protocol with communication complexity strictly less than n based on any one-way trapdoor permutation.
---
paper_title: Private Searching on Streaming Data

paper_content:

In this paper we consider the problem of private searching on streaming data, where we can efficiently implement searching for documents that satisfy a secret criteria (such as the presence or absence of a hidden combination of hidden keywords) under various cryptographic assumptions. Our results can be viewed in a variety of ways: as a generalization of the notion of private information retrieval (to more general queries and to a streaming environment); as positive results on privacy-preserving datamining; and as a delegation of hidden program computation to other machines.
---
paper_title: A Generalisation, a Simplification and some Applications of Paillier’s Probabilistic Public-Key System

paper_content:

We propose a generalisation of Paillier's probabilistic public key system, in which the expansion factor is reduced and which allows to adjust the block length of the scheme even after the public key has been fixed, without losing the homomorphic property. We show that the generalisation is as secure as Paillier's original system. We construct a threshold variant of the generalised scheme as well as zero-knowledge protocols to show that a given ciphertext encrypts one of a set of given plaintexts, and protocols to verify multiplicative relations on plaintexts. We then show how these building blocks can be used for applying the scheme to efficient electronic voting. This reduces dramatically the work needed to compute the final result of an election, compared to the previously best known schemes. We show how the basic scheme for a yes/no vote can be easily adapted to casting a vote for up to t out of L candidates. The same basic building blocks can also be adapted to provide receipt-free elections, under appropriate physical assumptions. The scheme for 1 out of L elections can be optimised such that for a certain range of parameter values, a ballot has size only O(log L) bits.
---
paper_title: Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP

paper_content:

Let \Lambda : {0, 1}^n ? {0, 1}^m \to {0, 1} be a Boolean formula of size d, or more generally, an arithmetic circuit of degree d, known to both Alice and Bob, and let y \in {0, 1}^m be an input known only to Alice. Assume that Alice and Bob interacted in the past in a preamble phase (that is, applied a preamble protocol that depends only on the parameters, and not on \Lambda, y). We show that Alice can (non-interactively) commit to y, by a message of size poly(m, log d), and later on prove to Bob any N statements of the form \Lambda(x_1, y) = z_1, . . . , \Lambda(x_{N}, y) = z_N by a (computationally sound) non-interactive zero-knowledge proof of size poly(d, logN). (Note the logarithmic dependence on N). We give many applications and motivations for this result. In particular, assuming that Alice and Bob applied in the past the (poly-logarithmic size) preamble protocol: 1. Given a CNF formula \Psi(w_1, . . . , w_m ) of size N, Alice can prove the satisfiability of \Psi by a (computationally sound) non-interactive zero-knowledge proof of size poly(m). That is, the size of the proof depends only on the size of the witness and not on the size of the formula. 2. Given a language L in the class LOGSNP and an input x \in {0,|1}^n , Alice can prove the membership x \in L by a (computationally sound) non-interactive zero-knowledge proof of size polylogn. 3. Alice can commit to a Boolean formula y of size m, by a message of size poly(m), and later on prove to Bob any N statements of the form y(x_1 ) = z_1 , . . . , y(x_N ) = z_N by a (computationally sound) non-interactive zero-knowledge proof of size poly(m, logN). Our cryptographic assumptions include the existence of a poly-logarithmic Symmetric-Private-Information- Retrieval (SPIR) scheme, as defined in [4], and the existence of commitment schemes, secure against circuits of size exponential in the security parameter.
---
paper_title: Software protection and simulation on oblivious RAMs

paper_content:

Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the theoretical treatment it deserves. In this paper, we provide theoretical treatment of software protection. We reduce the problem of software protection to the problem of efficient simulation on oblivious RAM. A machine is oblivious if thhe sequence in which it accesses memory locations is equivalent for any two inputs with the same running time. For example, an oblivious Turing Machine is one for which the movement of the heads on the tapes is identical for each computation. (Thus, the movement is independent of the actual input.) What is the slowdown in the running time of a machine, if it is required to be oblivious? In 1979, Pippenger and Fischer showed how a two-tape oblivious Turing Machine can simulate, on-line, a one-tape Turing Machine, with a logarithmic slowdown in the running time. We show an analogous result for the random-access machine (RAM) model of computation. In particular, we show how to do an on-line simulation of an arbitrary RAM by a probabilistic oblivious RAM with a polylogaithmic slowdown in the running time. On the other hand, we show that a logarithmic slowdown is a lower bound.
---
paper_title: On the Compressibility of NP Instances and Cryptographic Applications

paper_content:

We initiate the study of compression that preserves the solution to an instance of a problem rather than preserving the instance itself. Our focus is on the compressibility of NP decision problems. We consider NP problems that have long instances but relatively short witnesses. The question is, can one efficiently compress an instance and store a shorter representation that maintains the information of whether the original input is in the language or not. We want the length of the compressed instance to be polynomial in the length of the witness rather than the length of original input. Such compression enables to succinctly store instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed. We give a new classification of NP with respect to compression. This classification forms a stratification of NP that we call the VC hierarchy. The hierarchy is based on a new type of reduction called W-reduction and there are compression-complete problems for each class. Our motivation for studying this issue stems from the vast cryptographic implications compressibility has. For example, we say that SAT is compressible if there exists a polynomial p(middot, middot) so that given a formula consisting of m clauses over n variables it is possible to come up with an equivalent (w.r.t satisfiability) formula of size at most p(n, log m). Then given a compression algorithm for SAT we provide a construction of collision resistant hash functions from any one-way function. This task was shown to be impossible via black-box reductions (D. Simon, 1998), and indeed the construction presented is inherently non-black-box. Another application of SAT compressibility is a cryptanalytic result concerning the limitation of everlasting security in the bounded storage model when mixed with (time) complexity based cryptography. In addition, we study an approach to constructing an oblivious transfer protocol from any one-way function. This approach is based on compression for SAT that also has a property that we call witness retrievability. However, we mange to prove severe limitations on the ability to achieve witness retrievable compression of SAT
---
paper_title: Algebraic Lower Bounds for Computing on Encrypted Data

paper_content:

In cryptography, there has been tremendous success in building primitives out of homomorphic semantically-secure encryption schemes, using homomorphic properties in a black-box way. A few notable examples of such primitives include items like private information retrieval schemes and collision-resistant hash functions (e.g. [14, 6, 13]). In this paper, we illustrate a general methodology for determining what types of protocols can be implemented in this way and which cannot. This is accomplished by analyzing the computational power of various algebraic structures which are preserved by existing cryptosystems. More precisely, we demonstrate lower bounds for algebraically generating generalized characteristic vectors over certain algebraic structures, and subsequently we show how to directly apply this abstract algebraic results to put lower bounds on algebraic constructions of a number of cryptographic protocols, including PIR-writing and private keyword search protocols. We hope that this work will provide a simple “litmus test” of feasibility for use by other cryptographic researchers attempting to develop new protocols that require computation on encrypted data. Additionally, a precise mathematical language for reasoning about such problems is developed in this work, which may be of independent interest.
---
paper_title: Replication is not needed: single database, computationally-private information retrieval

paper_content:

We establish the following, quite unexpected, result: replication of data for the computational private information retrieval problem is not necessary. More specifically, based on the quadratic residuosity assumption, we present a single database, computationally private information retrieval scheme with O(n/sup /spl epsiv//) communication complexity for any /spl epsiv/>0.
---
paper_title: An oblivious transfer protocol with log-squared communication

paper_content:

We propose a one-round 1-out-of-n computationally-private information retrieval protocol for l-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computation and communication Θ(klog2n+llogn), where k is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private 1-out-of-n oblivious-transfer protocol for l-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model.
---
paper_title: Single Database Private Information Retrieval with Logarithmic Communication

paper_content:

We study the problem of single database private information retrieval, and present a solution with only logarithmic server-side communication complexity and a solution with only logarithmic user-side communication complexity. Previously the best result could only achieve polylogarithmic communication on each side, and was based on certain less well-studied assumptions in number theory [6]. On the contrary, our schemes are based on Paillier’s cryptosystem [16], which along with its variants have drawn extensive studies in recent cryptographic researches [3, 4, 8, 9], and have many important applications [7, 8].
---
paper_title: Replication is not needed: single database, computationally-private information retrieval

paper_content:

We establish the following, quite unexpected, result: replication of data for the computational private information retrieval problem is not necessary. More specifically, based on the quadratic residuosity assumption, we present a single database, computationally private information retrieval scheme with O(n/sup /spl epsiv//) communication complexity for any /spl epsiv/>0.
---
paper_title: A Generalisation, a Simplification and some Applications of Paillier’s Probabilistic Public-Key System

paper_content:

We propose a generalisation of Paillier's probabilistic public key system, in which the expansion factor is reduced and which allows to adjust the block length of the scheme even after the public key has been fixed, without losing the homomorphic property. We show that the generalisation is as secure as Paillier's original system. We construct a threshold variant of the generalised scheme as well as zero-knowledge protocols to show that a given ciphertext encrypts one of a set of given plaintexts, and protocols to verify multiplicative relations on plaintexts. We then show how these building blocks can be used for applying the scheme to efficient electronic voting. This reduces dramatically the work needed to compute the final result of an election, compared to the previously best known schemes. We show how the basic scheme for a yes/no vote can be easily adapted to casting a vote for up to t out of L candidates. The same basic building blocks can also be adapted to provide receipt-free elections, under appropriate physical assumptions. The scheme for 1 out of L elections can be optimised such that for a certain range of parameter values, a ballot has size only O(log L) bits.
---
paper_title: An oblivious transfer protocol with log-squared communication

paper_content:

We propose a one-round 1-out-of-n computationally-private information retrieval protocol for l-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computation and communication Θ(klog2n+llogn), where k is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private 1-out-of-n oblivious-transfer protocol for l-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model.
---
paper_title: Single Database Private Information Retrieval with Logarithmic Communication

paper_content:

We study the problem of single database private information retrieval, and present a solution with only logarithmic server-side communication complexity and a solution with only logarithmic user-side communication complexity. Previously the best result could only achieve polylogarithmic communication on each side, and was based on certain less well-studied assumptions in number theory [6]. On the contrary, our schemes are based on Paillier’s cryptosystem [16], which along with its variants have drawn extensive studies in recent cryptographic researches [3, 4, 8, 9], and have many important applications [7, 8].
---
paper_title: Universal one-way hash functions and their cryptographic applications

paper_content:

We define a Universal One-Way Hash Function family, a new primitive which enables the compression of elements in the function domain. The main property of this primitive is that given an element x . We prove constructively that universal one-way hash functions exist if any 1-1 one-way functions exist. Among the various applications of the primitive is a One-Way based Secure Digital Signature Scheme, a system which is based on the existence of any 1-1 One-Way Functions and is secure against the most general attack known. Previously, all provably secure signature schemes were based on the stronger mathematical assumption that trapdoor one-way functions exist.
---
paper_title: Computationally private information retrieval with polylogarithmic communication

paper_content:

We present a single-database computationally private information retrieval scheme with polylogarithmic communication complexity. Our construction is based on a new, but reasonable intractability assumption, which we call the φ-Hiding Assumption (φHA): essentially the difficulty of deciding whether a small prime divides φ(m), where m is a composite integer of unknown factorization.
---
paper_title: Single Database Private Information Retrieval with Logarithmic Communication

paper_content:

We study the problem of single database private information retrieval, and present a solution with only logarithmic server-side communication complexity and a solution with only logarithmic user-side communication complexity. Previously the best result could only achieve polylogarithmic communication on each side, and was based on certain less well-studied assumptions in number theory [6]. On the contrary, our schemes are based on Paillier’s cryptosystem [16], which along with its variants have drawn extensive studies in recent cryptographic researches [3, 4, 8, 9], and have many important applications [7, 8].
---
paper_title: Computationally private information retrieval with polylogarithmic communication

paper_content:

We present a single-database computationally private information retrieval scheme with polylogarithmic communication complexity. Our construction is based on a new, but reasonable intractability assumption, which we call the φ-Hiding Assumption (φHA): essentially the difficulty of deciding whether a small prime divides φ(m), where m is a composite integer of unknown factorization.
---
paper_title: Single-Database Private Information Retrieval with Constant Communication Rate

paper_content:

We present a single-database private information retrieval (PIR) scheme with communication complexity ${\mathcal O}(k+d)$, where k ≥ log n is a security parameter that depends on the database size n and d is the bit-length of the retrieved database block. This communication complexity is better asymptotically than previous single-database PIR schemes. The scheme also gives improved performance for practical parameter settings whether the user is retrieving a single bit or very large blocks. For large blocks, our scheme achieves a constant “rate” (e.g., 0.2), even when the user-side communication is very low (e.g., two 1024-bit numbers). Our scheme and security analysis is presented using general groups with hidden smooth subgroups; the scheme can be instantiated using composite moduli, in which case the security of our scheme is based on a simple variant of the “Φ-hiding” assumption by Cachin, Micali and Stadler [2].
---
paper_title: One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval

paper_content:

We show that general one-way trapdoor permutations are sufficient to privately retrieve an entry from a database of size n with total communication complexity strictly less than n. More specifically, we present a protocol in which the user sends O(K2) bits and the server sends n - cn/K bits (for any constant c), where K is the security parameter of the trapdoor permutations. Thus, for sufficiently large databases (e.g., when K = nƐ for some small Ɛ) our construction breaks the information-theoretic lower-bound (of at least n bits). This demonstrates the feasibility of basing single-server private information retrieval on general complexity assumptions. ::: ::: An important implication of our result is that we can implement a 1-out-of- n Oblivious Transfer protocol with communication complexity strictly less than n based on any one-way trapdoor permutation.
---
paper_title: Universal one-way hash functions and their cryptographic applications

paper_content:

We define a Universal One-Way Hash Function family, a new primitive which enables the compression of elements in the function domain. The main property of this primitive is that given an element x . We prove constructively that universal one-way hash functions exist if any 1-1 one-way functions exist. Among the various applications of the primitive is a One-Way based Secure Digital Signature Scheme, a system which is based on the existence of any 1-1 One-Way Functions and is secure against the most general attack known. Previously, all provably secure signature schemes were based on the stronger mathematical assumption that trapdoor one-way functions exist.
---

Title: A survey of single-database private information retrieval: techniques and applications

Section 1: Introduction
Description 1: Write an introduction describing the basics of Single-Database Private Information Retrieval (PIR), its purpose, and the naive solution.

Section 2: Single-Database PIR
Description 2: Discuss the history and foundational works of Single-Database PIR, including significant contributions and key techniques used.

Section 3: Amortizing Database Work in PIR
Description 3: Explain how to amortize the computational work in PIR for multiple queries and the techniques involved in achieving this.

Section 4: Connections: Single Database PIR and OT
Description 4: Outline the connection between Single-Database PIR and Oblivious Transfer (OT), detailing the similarities and transformations between the two.

Section 5: Connections: PIR and Collision-Resistant Hashing
Description 5: Describe how PIR protocols relate to collision-resistant hashing and the implications of this connection.

Section 6: Connections: PIR and Function-Hiding PKE
Description 6: Discuss the relationship between PIR and function-hiding public-key encryption, and the use cases where function-hiding PKE is relevant.

Section 7: Connections: PIR and Complexity Theory
Description 7: Explore the connections between PIR and various complexity theory problems, including secure function evaluation and zero-knowledge arguments.

Section 8: Public-Key Encryption That Supports PIR Read and Write
Description 8: Explain the concept of public-key encryption schemes that allow for PIR queries and data modifications with small communication complexity.

Section 9: Organization of the Rest of the Paper
Description 9: Provide an outline of the remaining sections of the paper and the main focus areas.

Section 10: Balancing the Communication Between Sender and Receiver
Description 10: Discuss techniques for minimizing communication complexity in PIR protocols and how to balance communication between sender and receiver.

Section 11: PIR Based on Group-Homomorphic Encryption
Description 11: Present various PIR protocols based on group-homomorphic encryption, highlighting the generic methods and specific cryptosystems used.

Section 12: Homomorphic Encryption Schemes
Description 12: Explain the principles of homomorphic encryption schemes and their role in constructing PIR protocols.

Section 13: PIR Based on the Φ-Hiding Assumption
Description 13: Introduce the Φ-Hiding Assumption and describe its application in developing PIR protocols with logarithmic communication.

Section 14: Preliminaries
Description 14: Provide the necessary algebraic and cryptographic preliminaries required to understand the PIR protocols based on the Φ-Hiding Assumption.

Section 15: A Brief Description of the Protocol
Description 15: Give a high-level overview of the PIR protocol based on the Φ-Hiding Assumption, including key algorithmic steps.

Section 16: Generalizations: Smooth Subgroups
Description 16: Discuss the generalizations of PIR protocols based on smooth subgroups, including more advanced techniques and optimizations.

Section 17: PIR from Any Trapdoor Permutation
Description 17: Describe the construction of PIR protocols based on general trapdoor permutations and the communication-balancing techniques used.

Section 18: Outline of the Protocol
Description 18: Provide a high-level outline of the PIR protocol based on trapdoor permutations.

Section 19: Sketch of Protocol Details
Description 19: Provide more detailed steps and explanations of the PIR protocol based on trapdoor permutations.

Section 20: Conclusions
Description 20: Summarize the main findings and contributions of the paper, and mention open problems and future research directions in Single-Database PIR.