PRIVATE INFORMATION RETRIEVAL WITH PROBABILISTIC BATCH CODES

• US 20190325082A1
• Filed: 04/19/2018
• Published: 10/24/2019
• Est. Priority Date: 04/19/2018
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Laine, Kim, Chen, Hao, Setty, Srinath T V, Angel, Sebastian
• Granted Patent: US 10,853,422 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

Systems, methods, and computer-executable instructions for reducing amortized computational costs for a query that includes receiving at least two indexes for elements stored in an n-element database. The n-element database is encoded into at least three buckets. Each element is stored within at least two buckets. Each bucket stores a proper subset of the n-elements. For each of the two indexes, a bucket is determined to retrieve the element at the index. The determined buckets are queried to retrieve the elements. The elements at the indexes are retrieved based on the querying the determined buckets.

Claims

1. A method for reducing amortized computational costs for a query, the method comprising operations performed using an electronic processor, the operations comprising:

receiving at least two indexes for elements stored in an n-element database, wherein the n-element database is encoded into at least three buckets, wherein each element is stored within at least two buckets, and wherein each bucket stores a proper subset of the n-elements;

determining, for each of the two indexes, a bucket to retrieve the element at the index;

querying the determined buckets to retrieve the elements; and

receiving the elements at the indexes based on the querying the determined buckets.

2. The method of claim 1, further comprising:

determining unqueried buckets; and

querying the unqueried buckets, wherein each of the at least three buckets is queried one time.

3. The method of claim 2, further comprising determining a first set of two indexes are stored in the same bucket for first elements.

4. The method of claim 3, further comprising selecting, based on the determining the first set of two indexes are stored in the same bucket, the elements, wherein the elements are different from the first elements, wherein the two indexes are different from the first set of two indexes.

5. The method of claim 1, wherein determining, for each of the two indexes, the bucket to retrieve the element at the index comprises simulating allocation for each of the two indexes to determine the bucket, wherein the determined bucket is one of the at least two buckets used to store the element.

6. The method of claim 1, wherein a bucket stores a combination of two elements, the method further comprising:

receiving the combination of two elements; and

computing one of the elements from the combination of two elements.

7. The method of claim 1, further comprising:

receiving at least two queries, wherein the queries comprise the at least two indexes, and wherein the at least two queries are ciphertexts; and

expanding the at least two queries into a plurality of ciphertexts.

8. The method of claim 7, further comprising concatenating the plurality of ciphertexts, wherein the concatenated plurality of ciphertexts is used to query the at least two indexes.

9. The method of claim 7, further comprising:

determining a column within the n-element database where an element is stored based on one of the at least two queries; and

determining a row within the n-element database where the element is stored based on a different one of the at least two queries, wherein the n-element database stores elements in a hypercube.

10. A system for reducing amortized computational costs for a query, the system comprising:

a plurality of buckets, wherein each bucket stores elements;

a server configured to;

setup a n-element database, wherein the n-element database stores an element in at least two of the plurality of buckets;

receive at least two indexes for elements stored in the n-element database,

query the plurality of buckets to retrieve the elements, wherein each of the plurality of buckets is queried,

receive the elements at the indexes based on the querying the determined buckets; and

return the elements

11. The system of claim 10, wherein the serv er is further configured to receive at least two queries, wherein the queries comprise the at least two indexes, and wherein the at least two queries are ciphertexts;

and expand the at least two queries into a plurality of ciphertexts.

12. The system of claim 11, wherein the server is further configured to concatenate the plurality of ciphertexts, wherein the concatenated plurality of ciphertexts is used to query the at least two indexes.

13. The system of claim 11, wherein the server is further configured to. determine a column within the n-element database where an element is stored based on one of the at least two queries, and determine a row within the n-element database where the element is stored based on a different one of the at least two queries, wherein the n-element database stores elements in a hypercube.

14. A computer-readable storage media storing computer-executable instructions for reducing amortized computational costs for a query, the stored instructions comprising:

instructions to receive at least two indexes for elements stored in an n-element database, wherein the n-element database is encoded into at least three buckets, wherein each element is stored within at least two buckets, and wherein each bucket stores a proper subset of the n-elements;

instructions to determine, for each of the two indexes, a bucket to retrieve the element at the index;

instructions to query the determined buckets to retrieve the elements; and

instructions to receive the elements at the indexes based on the querying the determined buckets.

15. The computer-readable storage media of claim 14, wherein the instructions further comprise:

instructions to determine unqueried buckets; and

instructions to query the unqueried buckets, wherein each bucket is queried one time.

16. The computer-readable storage media of claim 15, wherein the instructions further comprise instructions to determine a first set of two indexes are stored in the same bucket.

17. The computer-readable storage media of claim 16, wherein the instructions further comprise instructions to select, based on the determining the first set of two indexes are stored in the same bucket, the elements, wherein the elements are different from the first elements, and wherein the two indexes are different from the first set of two indexes.

18. The computer-readable storage media of claim 14, wherein the instructions to determine, for each of the two indexes, the bucket to retrieve the element at the index comprise instructions to simulate allocation for each of the two indexes to determine the bucket, wherein the determined bucket is one of the at least two buckets used to store the element.

19. The computer-readable storage media of claim 14, wherein a bucket stores a combination of two elements, wherein the instructions further comprise:

instructions to receive the combination of two elements; and

instructions to compute one of the elements from the combination of two elements.

20. The computer-readable storage media of claim 14, wherein the instructions further comprise:

instructions to receive at least two queries, wherein the queries comprise the at least two indexes, and wherein the at least two queries are ciphertexts; and

instructions to expand the at least two queries into a plurality of ciphertexts.