METHOD AND APPARATUS FOR COMMUNICATION EFFICIENT PRIVATE INFORMATION RETRIEVAL AND OBLIVIOUS TRANSFER

• US 20090193033A1
• Filed: 02/04/2009
• Published: 07/30/2009
• Est. Priority Date: 05/19/2005
• Status: Abandoned Application

• Current Assignee: Google Inc. (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gentry, Craig B., Ramzan, Zulfikar Amin
• Application Number:
  US12/365,840
• Publication Number:
  US 20090193033A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/50 Oblivious transfer
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems

Abstract

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.

Claims

1. A method comprising:

applying an oblivious transfer function to an input to produce an output;

applying a private retrieval process using the output of the oblivious transfer.

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

applying an oblivious transfer function to an input to produce an output;

applying a private retrieval process using the output of the oblivious transfer