Method and apparatus for communication efficient private information retrieval and oblivious transfer

1. A method of privately retrieving information from a database, the method comprising:

obtaining, by a client, an index corresponding to information to be retrieved from the database;

generating a query that avoids revealing the index to the database, the query being an arithmetic function of the index and a secret value that is an arithmetic function of the index, wherein the arithmetic function includes a multiplication group specified by a modulus of a random value whose order is divisible by a prime power, such that the prime power is an order of the random value, and wherein the secret value comprises the factorization into prime numbers of the modulus;

communicating the query to the database for execution of the arithmetic function against the entirety of the database; and

receiving, by the client, results from the database of the execution of the arithmetic function by the database.

2. The method defined in claim 1 further comprising applying a mapping to the database to obtain the prime power.

3. The method defined in claim 1 further comprising:

sampling the modulus according to a distribution function from a set of values that Φ-hide the prime power; and

generating the random value with an order being the prime power in the multiplicative group taken modulo the modulus.

4. The method defined in claim 1 further comprising:

applying a mapping to the index to obtain a prime power;

sampling a sufficiently large modulus according to a distribution function from a set of values that Φ-hide the prime power; and

generating a random value whose order is the prime power in the multiplicative group taken modulo the modulus.

5. The method defined in claim 1 wherein the query comprises O(log m) bits, wherein m equals the number of elements stored in the database.

6. The method defined in claim 1 further comprising:

decoding the results, wherein the total amount of information exchanged with the database is less than the total amount of information stored in the database.

7. An article of manufacture having one or more recordable media storing instructions thereon which, when executed by a system, cause the system to perform a method comprising:

obtaining an index corresponding to information to be retrieved from the database;

generating a query that avoids revealing the index to the database, the query being an arithmetic function of the index and a secret value, wherein the arithmetic function includes a multiplication group specified by a modulus of a random value whose order is divisible by a prime power, such that the prime power is an order of the random value, and wherein the secret value is an arithmetic function of the index and comprises the factorization into prime numbers of the modulus;

communicating the query to the database for execution of the arithmetic function against the entirety of the database; and

receiving results from the database of the execution of the arithmetic function by the database.

8. The article of manufacture defined in claim 7 wherein the method further comprises applying a mapping to the database to obtain the prime power.

9. The article of manufacture defined in claim 7 wherein the method further comprises:

sampling the modulus according to a distribution function from a set of values that Φ-hide the prime power; and

generating the random value with an order being the prime power in the multiplicative group taken modulo the modulus.

10. The article of manufacture defined in claim 7 wherein the method further comprises:

applying a mapping to the index to obtain a prime power;

sampling a sufficiently large modulus according to a distribution function from a set of values that Φ-hide the prime power; and

generating a random value whose order is the prime power in the multiplicative group taken modulo the modulus.

11. The article of manufacture defined in claim 7 wherein the query comprises O(log m) bits, wherein m equals the number of elements stored in the database.

12. The article of manufacture defined in claim 7 wherein the method further comprises:

decoding the results, wherein the total amount of information exchanged with the database is less than the total amount of information stored in the database.

13. An apparatus comprising: an external network interface

through which a request for information is made; a memory; and a processor, coupled to the external network interface and the memory, to:

obtain an index corresponding to the information to be retrieved from the database;

generate a query that avoids to reveal the index to the database, the query being an arithmetic function of the index and a secret value that is an arithmetic function of the index, wherein the arithmetic function includes a multiplication group specified by a modulus of a random value whose order is divisible by a prime power, such that the prime power is an order of the random value, and wherein the secret value comprises the factorization into prime numbers of the modulus; and

communicate the query to the database for execution of the arithmetic function against the entirety of the database; and

receive results from the database of the execution of the arithmetic function by the database.

14. The apparatus defined in claim 13 wherein the processor applies a mapping to the index to obtain a prime power, samples a sufficiently large modulus according to a distribution function from a set of values that Φ-hide the prime power, and generates a random value whose order is the prime power in the multiplicative group taken modulo the modulus.