Method and apparatus for communication efficient private information retrieval and oblivious transfer
View Patent ↗A method, article of manufacture and apparatus for performing private retrieval of information from a database is disclosed. In one embodiment, the method comprising obtaining an index corresponding to information to be retrieved from the database and generating a query that does not reveal the index to the database. The query is 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. The secret value is an arithmetic function of the index that comprises a factorization into prime numbers of the modulus. The method further comprises communicating the query to the database for execution of the arithmetic function against the entirety of the database.
1. A polylogarithmic single database computational private information retrieval process comprising:
generating a query that encodes the index into an arithmetic function to avoid revealing to the database the index;
communicating the query to the database for execution of the arithmetic function against the entirety of the database;
receiving results of the execution of the arithmetic function from the database, wherein the total amount of information exchanged with the database is within a constant factor of the logarithm of the size of the database; and
performing reconstruction on the results by:
determining a first value by exponentiating a first input base to a power equal to a function applied to a modulus divided by a prime power associated with a specified index and performing a modulo operation using a modulus on a result of exponentiating the first input base,
determining a second value by exponentiating a second input base to the prime power and performing a modulo operation using the modulus on a result of exponentiating the first input base,
arithmetically determining a third value based on a discrete logarithm of the second value with respect to a base equal to the first value, and generating at least one bit associated with the query from the third value.
2. The process defined in claim 1
wherein the function is the Euler totient function.
3. The process defined in claim wherein the first, second and third values are computed off-line.
4. The process defined in claim 1 wherein the query comprises O(log m) bits, wherein m equals the number of elements stored in the database.
5. A polylogarithmic single database computational private information retrieval process comprising:
generating a query that encodes the index into an arithmetic function to avoid revealing to the database the index, wherein the query comprises 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;
communicating the query to the database for execution of the arithmetic function against the entirety of the database;
receiving results of the execution of the arithmetic function from the database, wherein the total amount of information exchanged with the database is within a constant factor of the logarithm of the size of the database.
6. The process defined in claim 5 wherein the prime power is an order of the random value, and wherein the secret value comprises the factorization into prime numbers of the modulus.
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 polylogarithmic single database computational private information retrieval process comprising:
generating a query that encodes the index into an arithmetic function to avoid revealing to the database the index;
communicating the query to the database for execution of the arithmetic function against the entirety of the database;
receiving results of the execution of the arithmetic function from the database, wherein the total amount of information exchanged with the database is within a constant factor of the logarithm of the size of the database; and
performing reconstruction on the results by
determining a first value by exponentiating a first input base to a power equal to a function applied to a modulus divided by a prime power associated with a specified index and performing a modulo operation using a modulus on a result of exponentiating the first input base,
determining a second value by exponentiating a second input base to the prime power and performing a modulo operation using the modulus on a result of exponentiating the first input base,
arithmetically determining a third value based on a discrete logarithm of the second value with respect to a base equal to the first value, and
generating at least one bit associated with the query from the third value.
8. The article of manufacture defined in claim 7 wherein the function is a Euler totient function.
9. The article of manufacture defined in claim 7 wherein the first, second and thrid values are computed off-line.
10. 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.
11. 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 polylogarithmic single database computational private information retrieval process comprising:
generating a query that encodes the index into an arithmetic function to avoid revealing to the database the index, wherein the query comprises 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;
communicating the query to the database for execution of the arithmetic function against the entirety of the database;
receiving results of the execution of the arithmetic function from the database, wherein the total amount of information exchanged with the database is within a constant factor of the logarithm of the size of the database.
12. The article of manufacture defined in claim 11 wherein the prime power is an order of the random value, and wherein the secret value comprises the factorization into prime numbers of the modulus.
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:
generate a query that encodes the index into an arithmetic function to avoid revealing to the database the index, wherein the query comprises 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;
communicate the query to the database for execution of the arithmetic function against the entirety of the database;
receive results of the execution of the arithmetic function from the database, wherein the total amount of information exchanged with the database is within a constant factor of the logarithm of the size of the database.
14. The apparatus defined in claim 13 wherein the prime power is an order of the random value, and wherein the secret value comprises the factorization into prime numbers of the modulus.
15. The apparatus defined in claim 13 wherein the query comprises O(log m) bits, wherein m equals the number of elements stored in the database.