Secure multi-party information retrieval

Patent metadata

Field	Value
Publication number	US-11775656-B2
Application number	US-201515567531-A
Country	US
Kind code	B2
Filing date	May 1, 2015
Priority date	May 1, 2015
Publication date	Oct 3, 2023
Grant date	Oct 3, 2023

Abstract

Secure multi-party information retrieval is disclosed. One example is a system including a query processor to request secure retrieval of candidate terms similar to a query term. A collection of information processors, where a given information processor receives the request and generates a random permutation. A plurality of data processors, where a given data processor generates clusters of a plurality of terms in a given dataset, where the clusters are based on similarity scores for pairs of terms, and selects a representative term from each cluster. The given information processor determines similarity scores between a secured query term received from the query processor and secured representative terms received from the given data processor, where the secured terms are based on the permutation, and the given data processor filters, without knowledge of the query term, the candidate terms of the plurality of terms based on the determined similarity scores.

First claim

The invention claimed is:

1. A system comprising:
a query processor to request secure retrieval of candidate terms similar to a query term in a query dataset, the query processor comprising at least one hardware component;
a collection of information processors, wherein a given information processor is to receive the request and generate a random permutation based on the request;
a plurality of data processors, wherein a given data processor is to generate clusters of a plurality of terms in a given dataset, based on similarity scores for pairs of terms, and is to select a representative term from each cluster; and wherein:
the given information processor is to determine similarity scores between a secured query term received from the query processor and secured representative terms received from the given data processor, the secured representative terms based on the random permutation, and
the given data processor is to filter, without knowledge of the query term, the candidate terms of the plurality of terms based on the determined similarity scores.

2. The system of claim 1 , wherein the given data processor generates the secured representative terms by applying an orthogonal transform to each term, and by truncating a portion of the transformed term, the truncated portion being based on the given information processor.

3. The system of claim 1 , wherein the given information processor is to:
associate each candidate term with a ranked term identifier, wherein the ranked term identifier is based on the determined similarity scores; and
provide, to the query processor, a plurality of ranked term identifiers.

4. The system of claim 3 , wherein the collection of information processors is to provide to the query processor, an aggregate ranking of the plurality of ranked term identifiers from each processor, aggregated over all processors of the collection of information processors.

5. The system of claim 3 , wherein the query processor is to select top-k term identifiers from the plurality of ranked term identifiers.

6. The system of claim 1 , wherein the given data processor is to filter the candidate terms based on a confidence threshold for similarity distributions between the secured query term and a plurality of secured representative terms.

7. The system of claim 6 , wherein the similarity distributions have a hypergeometric distribution.

8. The system of claim 1 , wherein:
the query processor is to further request secure retrieval of additional candidate terms similar to a second query term;
the given information processor is to determine additional similarity scores between a secured second query term and the secured representative terms; and
the given data processor is to filter, without knowledge of the second query term, the additional candidate terms of the plurality of terms based on the determined additional similarity scores.

9. A method for secure multi-party information retrieval, the method comprising:
receiving, at a given information processor of a collection of information processors, a request from a query processor to securely retrieve candidate terms similar to a query term in a query dataset;
generating, for a given data processor of a plurality of data processors, clusters of a plurality of terms in a given dataset, the clusters based on similarity scores for pairs of terms;
selecting a representative term from each cluster, wherein the representative term is a medoid of the respective cluster;
generating, at the given information processor, a random permutation based on the request;
determining, at the given information processor, similarity scores between a secured query term received from the query processor and secured representative terms received from the given data processor, the secured representative terms based on the random permutation;
filtering, at the given data processor and without knowledge of the secured query term, the candidate terms of the plurality of terms based on the determined similarity scores; and
providing the candidate terms to the given information processor.

10. The method of claim 9 , further comprising ranking, for the given information processor, the candidate terms based on the similarity scores.

11. The method of claim 10 , further comprising:
associating each ranked term identifier with a candidate term; and
providing, to the query processor, a plurality of ranked term identifiers.

12. The method of claim 11 , further comprising selecting, by the query processor, top-k term identifiers from the plurality of ranked term identifiers.

13. The method of claim 11 , wherein the collection of information processors provides to the query processor, an aggregate ranking of the plurality of ranked term identifiers, aggregated over all processors of the collection of information processors.

14. The method of claim 9 , wherein the filtering the candidate terms is based on a confidence threshold for similarity distributions between the secured query term and the secured representative terms.

15. A non-transitory computer readable medium comprising executable instructions to:
initiate a request, from a query processor, for secure retrieval of candidate terms similar to a query term in a query dataset;
receive the request at a given information processor of a collection of information processors;
generate, at a given data processor of a plurality of data processors, clusters of a plurality of terms in a given dataset, based on similarity scores for pairs of terms;
select a representative term from each cluster;
generate, at the given information processor, a random permutation based on the request;
determine, at the given information processor, similarity scores between a secured query term received from the query processor and secured representative terms received from the given data processor, the secured representative terms based on the random permutation; and
filter, at the given data processor and without knowledge of the secured query term, the candidate terms of the plurality of terms based on the determined similarity scores.

16. The non-transitory computer readable medium of claim 15 , comprising executable instructions to:
generate, by the given data processor, the secured representative terms by applying an orthogonal transform to each term, and by truncating a portion of the transformed term, the truncated portion being based on the given information processor.

17. The non-transitory computer readable medium of claim 15 , comprising executable instructions to:
associate, by the given information processor, each candidate term with a ranked term identifier, wherein the ranked term identifier is based on the determined similarity scores; and
provide, by the given information processor, a plurality of ranked term identifiers to the query processor.

18. The non-transitory computer readable medium of claim 17 , comprising executable instructions to:
wherein the collection of information processors is to provide to the query processor, an aggregate ranking of the plurality of ranked term identifiers from each processor, aggregated over all processors of the collection of information processors.

19. The non-transitory computer readable medium of claim 17 , comprising executable instructions to:
select, by the query processor, top-k term identifiers from the plurality of ranked term identifiers.

20. The non-transitory computer readable medium of claim 15 , comprising executable instructions to:
filter, by the given data

Assignees

• Entit Software Llc
• Micro Focus Llc

Inventors

• Kafai Mehran
• Shang Hongwei
• Mitchell April Slayden

Classifications

• G06F21/602 Primary

  Providing cryptographic facilities or services · CPC title

• G06F16/24578

  using ranking · CPC title

• G06F21/6227

  where protection concerns the structure of data, e.g. records, types, queries · CPC title

• G06F21/6254

  by anonymising data, e.g. decorrelating personal data from the owner's identification · CPC title

• H04L9/3239

  involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD · CPC title