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.