Patent ID: 8065332

Claim:
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.