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:
determining a first value by exponentiating a first input base to a power equal to the Euler totient 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 method defined in claim 1 wherein the first, second and third values are computed off-line.
3. 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:
determining a first value by exponentiating a first input base to a power equal to the Euler totient 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.
4. The article of manufacture defined in claim 3 wherein the first, second and third values are computed off-line.
5. 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:
determine a first value by exponentiating a first input base to a power equal to the Euler totient 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;
determine 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 determine a third value based on a discrete logarithm of the second value with respect to a base equal to the first value; and
generate at least one bit associated with the query from the third value.