A survey of single-database private information retrieval: techniques and applications <s> Generalizations: Smooth Subgroups <s> 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. <s> BIB001 </s> A survey of single-database private information retrieval: techniques and applications <s> Generalizations: Smooth Subgroups <s> 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]. <s> BIB002
More recently, Gentry and Ramzan BIB002 have generalized some of the fundamental ideas behind these methods, creating protocols based on smooth subgroups, which are those that have many small primes dividing their order. Somewhat similar to CMS BIB001 , a list of primes is chosen corresponding to the positions of the database, and a query for position i essentially consists of a description of a group G such that |G| is divisible by p i . However, the work of BIB002 is designed to retrieve blocks of data at a single time (CMS BIB001 must be repeatedly executed to accomplish this functionality). Rather than repeatedly exponentiating by all of the primes, the database is represented as an integer e such that when reduced mod p i , the value is the i-th block of the database (such an integer always exists of course by the Chinese Remainder Theorem). Now to recover the data (which is just e mod p i ), a discrete log computation can be made in the (small) subgroup of order p i .