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 method comprising:
representing each of a plurality of groups of a database as an integer;
computing an integer value that is congruent to each integer representation of each of the plurality of groups modulo a prime power associated with an index of said each group;
receiving a database query over a network; and
generating a response to the database query by exponentiating a base input value provided with an exponent equal to the integer value modulo a modulus value.
2. The method defined in claim 1 further comprising partitioning the database into the plurality of groups.
3. The method defined in claim 1 wherein partitioning the database into a plurality of groups, representing each of the groups as an integer, and computing the integer value are performed off-line.
4. The method defined in claim 1 wherein the response comprises O(log m) bits, wherein m equals the number of elements stored in the database.
5. 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:
representing each of a plurality of groups of a database as an integer;
computing an integer value that is congruent to each integer representation of each of the plurality groups modulo a prime power associated with an index of said each group;
a database query over a network; and
generating a response to the database query by exponentiating a base input value provided with an exponent equal to the integer value modulo operation a modulus value.
6. The article of manufacture defined in claim 5 wherein the method further comprises partitioning the database into the plurality of groups.
7. The article of manufacture defined in claim 5 wherein partitioning the database into a plurality of groups, representing each of the groups as an integer, and computing the integer value are performed off-line.
8. The article of manufacture defined in claim 5 wherein the response comprises O(log m) bits, wherein m equals the number of elements stored in the database.
9. 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:
represent each of a plurality of groups of a database as an integer;
compute an integer value that is congruent to each integer representation of each of the plurality of groups modulo a prime power associated with an index of said each group;
receive a database query over a network; and
generate a response to the database query by exponentiating a base input value provided with an exponent equal to the integer value modulo operation a modulus value.