Private information retrieval
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.
1 Assignment
0 Petitions
Accused Products
Abstract
Method for retrieving data from a database, while assuring privacy, which comprises providing a database address for the data sought to be retrieved, generating at least two messages and communicating them to two or more database copies, generating two replies from the database copies, wherein one or more of said messages depends on the database address, a pseudo random or random number and wherein each reply depends on the message transmitted to the specific database copy, and the retrieved data is calculated as a function of said replies.
99 Citations
18 Claims
-
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 Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
- 1) data item from a database whilst essentially assuring the user'"'"'s privacy;
-
10. 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 DB0 -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;
each one of said database copies is organized in d dimensions (d≧
1) such that 2d =k and wherein each l-bit-long data item, stored therein, is associated with a database address of d indices (index1, . . . indexd);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 d-indices (i1, . . . id) database address of said sought data item; (ii) generating a string of d substrings S10, . . . Sd0 holding respectively a 1st to dth sets of indices;
said 1st to dth sets of indices, when applied to said DB0, defining a plurality of database addresses of respective plurality of l-bit-long data items stored therein;(iii) generating k-1 different strings having, respectively, string numbers 1 to k-1, wherein each string having d substrings S1.sup.σ
1, . . . sd.sup.σ
d, such that σ
1, . . . σ
d being a d-bit representation of the string number i of said string (i=1 . . . k-1);
said d substrings S1.sup.σ
1, . . . Sd.sup.σ
d, of each string having string number i (i=1 . . . k-1) holding, respectively, a 1st to dth sets of indices that when applied to DBi, having the same index i (i=1 . . . k-1), define a plurality of database addresses of respective plurality of l-bit-long data items stored in said DBi ;
each substring Sj.sup.σ
j from among said d substrings S1.sup.σ
1, . . . Sd.sup.σ
d (j=1 . . . d), has a value of either Sj0 (σ
j=
0) or Sj1 (σ
j=
1), wherein the former being the same as Sj0 from among said S10, . . . Sd0 stipulated in step (ii), and the latter (Sj1) equals to Sj0 ⊕
ij, wherein ij being an jth index taken from the indices (i1, . . . id) of the database address stipulated in step (i);(iv) for each database DBi, from among said databases DB0 to DBk-1, xoring, bit-by-bit the plurality of l-bit-long data items that are defined by the like number of plurality of database addresses applied to said DBi, as stipulated in said step (iii), so as to yield l-bit-long resulti, giving rise to the generation of k l-bit-long results from DB0 to DBk-1, respectively; (v) communicating the k l-bit-long results to the user; and (vi) the user xoring bit-by-bit said k l-bit-long results thereby deriving said sought data item. - View Dependent Claims (11, 12, 13, 14)
- 1) data item from a database whilst essentially assuring the user'"'"'s privacy;
-
15. A method for retrieving at least one sought l-bit-long 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;
each one of said database copies is organized in d dimensions (d≧
1) such that 2d =k and wherein each l-bit-long data item, stored therein, is associated with a database address of d indices (index1, . . . indexd);
k'"'"'(k'"'"'<
k) database copies (DBi.sbsb.0 . . . , DBi.sbsb.k'"'"'-1), from among said k database copies, being real and are further having respective indices numbers i0 . . . ik'"'"'-1 ;
the indices numbers i0 . . . ik'"'"'-1 taken from the numbers 0 to k-1;
the indices numbers i0 . . . ik'"'"'-1, form collectively k'"'"' codewords for covering k indices 0 . . . k-1, of d-bits each, with Hamming distance 1, thereby enabling (DBi.sbsb.0 . . . , DBi.sbsb.k'"'"'-1) to emulate the remaining k-k'"'"' database copies, from among said DB0 to DBk-1 ;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 d-indices (i1, . . . id) database address of said sought data item; (ii) generating a string of d substrings S1.sup.σ
1'"'"', . . . Sd.sup.σ
d'"'"' holding respectively a 1st to dth sets of indices;
said 1st to dth sets of indices, when applied to said DBi.sbsb.0, defining a plurality of database addresses of l-bit-long data items stored therein;
σ
1'"'"', . . . σ
d'"'"' being a d-bit representation of the string number i0 ;(iii) generating k'"'"'-1 (k'"'"'<
k) different strings having, respectively, string numbers i1 to ik'"'"'-1 being identical to said indices numbers i1 to ik'"'"'-1, wherein each string having d substrings S1.sup.σ
1, . . . Sd.sup.σ
d, such that σ
1, . . . σ
d being a d-bit representation of the string number ii of said string (ii =ii . . . ik-1);
said d substrings S1.sup.σ
1, . . . Sd.sup.σ
d, of each string having string number ii (ii =i1 . . . , ik'"'"'-1), holding respectively a 1st to dth sets of indices that when applied to DBi.sbsb.i, having the same index i (i=1 . . . k-1), define a plurality of database addresses of data items stored in said DBi.sbsb.i ;
each substring Sj.sup.σ
j from among said d substrings S1.sup.σ
1, . . . Sd.sup.σ
d (j=1 . . . d), has a value of either Sj.sup.σ
j'"'"' (σ
j =σ
j'"'"') or Sj.sup.σ
j'"'"' (σ
j ≠
σ
j'"'"'), wherein the former being the same as Sj.sup.σ
j'"'"' from among said Sj.sup.σ
1'"'"', . . . Sd.sup.σ
d'"'"' stipulated in step (ii), and the latter (Sj.sup.σ
j'"'"') being equal to Sj.sup.σ
j'"'"' ⊕
ij'"'"' wherein ij being an jth index taken from the d indices (i1, . . . id) of the database address stipulated in step (i);(iv) each database DBi.sbsb.1 from among said databases DBi.sbsb.0 . . . DBi.sbsb.k'"'"'-1, xoring bit-by-bit the plurality of l-bit-long data items that are defined by the like number of plurality of database addresses applied to said DBi.sbsb.1, as stipulated in said step (iii), so as to yield l-bit-long resulti ;
giving rise to the generation of k'"'"' l-bit-long results from DBi.sbsb.0 . . . DBi.sbsb.k'"'"'-1, respectively;(v) communicating the k'"'"' l-bit-long results of (iv) to the user; (vi) each one of the k'"'"' databases DBi.sbsb.0 . . . DBi.sbsb.k'"'"'-1 emulating the reply of every database DBj, from among said emulated databases, such that the index j thereof is of Hamming distance 1 with respect to the index of said one database;
the reply of each emulated database DBj, including repeatedly executing n1/d times said step (iv), each time with respect to a different database address, thereby generating n1/d l-bit-long results with respect to said DBj ;
giving rise to the generation of n1/d l-bit-long results with respect to each one of the k-k'"'"' emulated databases;(vii) communicating the k'"'"' l-bit-long results of (vi) to the user; (viii)for each one of said emulated k-k'"'"' DBj, the user selecting the correct l-bit-long result, from among said n1/d l-bit-long results, thereby obtaining k-k'"'"' l-bit-long results, which together with the k'"'"' l-bit-long results, stipulated in said step (iv), constitute k l-bit-long results; and (ix) the user xoring bit-by-bit said k l-bit-long results thereby deriving the sought data item.
- the database having k (k≧
-
16. A method for retrieving at least one sought data item from a database whilst essentially assuring the user'"'"'s privacy;
-
the database having k (k≧
2) database copies designated as DB0 -DBk-1 having respective k indices 0 . . . k-1;the method comprising the following steps executed with respect to each one of said at least one sought data item; (i) the providing a database address of the sought l-bit-long data item; (ii) the user generating at least two messages and communicating the messages to respective at least two database copies from among said DB0 -DBk-1 ; (iii) the at least two database copies generating at least two respective replies, and communicating the at least two replies to; wherein; at least one of said messages depends on at least the following parameters (a) and (b); (a) the database address stipulated in step (i), and (b) a pseudo random or random number; and
at least one of said messages depends on at least(c) a pseudo random or random number; and
wherein;each reply, from among said at least two replies, that is communicated from the respective database copy depends at least on the message communicated to said at respective database copy; and (iv) calculating the sought data item as a function of at least; (d) the at least two respective replies stipulated in said step (iii). - View Dependent Claims (17)
-
-
18. A system 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 system comprising a user station, linked to a communication channel, which includes in combination; (i) storage medium for storing a database address of said sought l-bit-long data item; (ii) string generator for generating k strings S0 . . . Sk-1, which when communicated and applied to databases copies DB0 to DBk-1, respectively, define in each one of them, a 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 associated with said data item;the system further comprising database processor that includes; (i) calculator associated with each database DBi, from among said databases DB0 . . . DBk-1, for calculating a respective resulti as a function of the plurality of said l-bit-long data items;
said calculator is further capable of communicating k results from DB0 . . . DBk-1, respectively; andin the user station, receiver for receiving said k results, and user calculator means associated with said receiver, for calculating the sought l-bit-long item as the function of said k results.
- 1) data item from a database whilst essentially assuring the user'"'"'s privacy;
Specification