×

Private information retrieval

  • US 5,855,018 A
  • Filed: 10/18/1996
  • Issued: 12/29/1998
  • Est. Priority Date: 10/20/1995
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for retrieving at least one sought l-bit-long (l≧

  • 1) data item from a database whilst essentially assuring the user'"'"'s privacy;

    the database having k (k≧

    2) database copies designated as DB00 -DBk-1 having respective k indices 0 . . . k-1;

    each of said database copies includes a plurality of l-bit-long data items associated, each, with a unique database address;

    the method comprising the following steps executed with respect to each one of said at least one sought l-bit-long data item;

    (i) providing a database address of said sought l-bit-long data item;

    (ii) generating k strings S0 . . . Sk-1, which when applied, each, to the respective databases DB0 to DBk-1, define in each one of them, a respective plurality of database addresses of a plurality of l-bit-long data items;

    the plurality of database addresses that is defined by each one of said S0 . . . Sk-1 containing a common subset and a complementary subset of database addresses;

    the respective complementary subsets of database addresses of S0 -Sk-1, being distinguishable, one with respect to the other, contingent upon the database address stipulated in step (i);

    (iii) calculating for each database DBi, from among said databases DB0 . . . DBk-1, resulti as a function of the plurality of l-bit-long data items of step (ii), giving rise to the generation of k results from DB0 . . . DBk-1, respectively;

    (iv) communicating the k results of (iii) to the user; and

    (v) calculating the sought l-bit-long item as a function of said k results.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×