1. A method of privately retrieving information from a database, the method comprising: obtaining, by a client, an index corresponding to information to be retrieved from the database; generating a query that avoids revealing the index to the database, the query being 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, such that the prime power is an order of the random value, and wherein the secret value comprises the factorization into prime numbers of the modulus; communicating the query to the database for execution of the arithmetic function against the entirety of the database; and receiving, by the client, results from the database of the execution of the arithmetic function by the database.