Private information retrieval with probabilistic batch codes
AssigneeMicrosoft Technology Licensing, LLC
InventorsKim Laine, Hao Chen, Srinath T V Setty, Sebastian Angel
Life of this patent
Estimating the term…
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.
Claims20
A method comprising operations performed using an electronic processor, the operations comprising:
- receiving an encrypted vector including at least two indexes corresponding to an element of elements stored in an n-element database, wherein the n-element database is encoded into at least three buckets, wherein each element of the elements in the n-element database is stored within at least two of the at least three buckets, and wherein each bucket of the at least three buckets stores a proper subset of the n-elements;
- determining, for each of the at least two indexes and based on values of the encrypted vector, a respective bucket to retrieve a first portion of the element at one of the at least two indexes and a second respective bucket to retrieve a second portion of the element at another of the at least two indexes;
- querying the determined respective buckets to retrieve the element portions using a homomorphic search;
- and
- receiving the element portions from the at least two indexes based on the querying the determined respective buckets using the homomorphic search.
A system comprising:
- a plurality of buckets, wherein each bucket stores elements and wherein each bucket stores a proper subset of n-elements;
- a server configured to:
- setup a n-element database, wherein each element of the elements in the n-element database is stored in at least two of the plurality of buckets;
- receive an encrypted vector including at least two indexes corresponding to an element of elements stored in the n-element database;
- determine, for each of the at least two indexes and based on values of the encrypted vector, a respective bucket to retrieve a first portion of the element at one of the at least two indexes and a second respective bucket to retrieve a second portion of the element at another of the at least two indexes;
- query the determined respective buckets to retrieve the element portions using a homomorphic search;
- receive the element portions from the at least two indexes based on the querying the determined respective buckets using the homomorphic search;
- and
- return the elements.
A computer-readable storage media storing computer-executable instructions, the stored instructions comprising:
- instructions to receive an encrypted vector including at least two indexes corresponding to an element of elements stored in an n-element database, wherein the n-element database is encoded into at least three buckets, wherein each element of the elements in the n-element database is stored within at least two of the at least three buckets, and wherein each bucket of the at least three buckets stores a proper subset of the n-elements;
- instructions to determine, for each of the at least two indexes and based on values of the encrypted vector, a respective bucket to retrieve a first portion of the element at one of the at least two indexes and a second respective bucket to retrieve a second portion of the element at another of the at least two indexes:
- instructions to query the determined respective buckets to retrieve the element portions using a homomorphic search;
- and
- instructions to receive the element portions from the at least two indexes based on the querying the determined respective buckets using the homomorphic search.
Dependencies are inferred from the claim text.