Searching for secret data through an untrusted searcher

Patent metadata

Field	Value
Publication number	US-9817899-B2
Application number	US-201314010104-A
Country	US
Kind code	B2
Filing date	Aug 26, 2013
Priority date	Aug 26, 2013
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

Abstract

Embodiments of the present invention relate to searching for secret data through an untrusted searcher without exposing the secret data. In one embodiment, a method of and computer program product for searching for secret data through an untrusted searcher is provided. A secret value is read from a storage medium. The secret value is divided into a plurality of portions. Each of the plurality of portions is ranked. A subset of the secret value is determined from the ranking of the plurality of portions. A search string is constructed from the subset. The search string is transmitted to a searcher via a network. Search results are received from the searcher via the network. The search results are compared to the secret value to determine whether the searcher found the secret value.

First claim

What is claimed is:

1. A method comprising:
reading a secret value from a storage medium, wherein the secret value includes a sequence of words;
extracting a plurality of portions from the secret value, wherein a first certain portion of the secret value includes a first word of the sequence of words, and wherein a second certain portion of the secret value includes a second word of the sequence of words;
ranking each of the plurality of portions;
determining a subset of the secret value from the ranking of the plurality of portions, wherein the subset of the secret value includes a word of the sequence of words;
constructing a search string from the subset;
transmitting the search string to a searcher via a network;
receiving search results from the searcher via the network;
analyzing the search results to determine that there is a match between data of the search results and data of the secret value, wherein the analyzing is performed by the owner of the secret value; and
based on the match being determined initiating a change of the secret value, wherein the transmitting and the receiving are performed by a trusted party, and wherein a search by the searcher is performed so that knowledge of the secret value is limited to the trusted party, wherein the searcher is an untrusted party that provides to the trusted party additional context surrounding any search hits to facilitate ascertaining by the trusted party whether a search hit corresponds with an instance of the secret value, and wherein the searcher is provided by a search engine that has access to a plurality of digital resources.

2. The method of claim 1 , wherein ranking comprises:
determining a likelihood that each of the plurality of portions occurs in a body of data except as part of the secret value.

3. The method of claim 1 , wherein ranking comprises:
comparing each of the plurality of portions to a list comprising a second plurality of portions; and
assigning a predetermined rank to those of the plurality of portions contained in the list.

4. The method of claim 1 , wherein ranking comprises: applying a pseudorandom function to each of the plurality of portions.

5. The method of claim 1 , wherein the secret value includes a passphrase.

6. The method of claim 1 , further comprising:
transmitting a context specification to the searcher; and
receiving context information from the searcher.

7. The method of claim 6 , wherein the context specification specifies a plurality of metadata requested and the context information comprises the plurality of metadata.

8. The method of claim 1 , wherein constructing the search string comprises:
introducing errors into the subset.

9. The method of claim 1 , wherein constructing the search string comprises:
adding additional search terms not included in the secret.

10. The method of claim 1 , wherein determining the subset comprises:
generating a plurality of candidate subsets;
ranking the candidate subsets; and
selecting the best ranked subset.

11. The method of claim 1 , where the method includes retaining content of the secret value as secret not subject to searching by the searcher.

12. The method of claim 1 , wherein the subset is a subsequence of words of the sequence of words.

13. The method of claim 1 , wherein the trusted party is the owner of the secret value.

14. The method of claim 1 , wherein the digital resources are provided by one or more of the following selected from the group consisting of: a document repository, a database, a file system, web pages, a social media outlet, forensic lab equipment, machine-readable memory, a network monitor, and a bus monitor.

15. The method of claim 1 , wherein constructing the search string comprises concatenating the subset.

16. A computer program product for searching for secret data, the computer program product comprising a computer readable storage device having program code embodied therewith, the program code when executed by a processor to:
read a secret value from a storage medium, wherein the secret value includes a sequence of words;
extract a plurality of portions from the secret value, wherein a first certain portion of the secret value includes a first word of the sequence of words, and wherein a second certain portion of the secret value includes a second word of the sequence of words;
rank each of the plurality of portions;
determine a subset of the secret value from the ranking of the plurality of portions, wherein the subset of the secret value includes a word of the sequence of words;
construct a search string from the subset;
transmit by a trusted party the search string to an untrusted searcher via a network;
receive by the trusted party search results from an untrusted searcher via the network;
analyze the search results to determine that there is a match between data of the search results and data of the secret value; and
based on the match initiate a change of the secret value, wherein a search by the untrusted searcher is performed so that knowledge of the secret value is limited to the trusted party, wherein the untrusted searcher provides to the trusted party additional context surrounding any search hits to facilitate ascertaining by the trusted party whether a search hit corresponds with an instance of the secret value, and wherein the untrusted searcher is provided by a search engine that has access to a plurality of digital resources.

17. The computer program product of claim 16 , wherein construct function includes a function to add additional search terms not included in the secret.

18. The computer program product of claim 16 , wherein the secret value comprises a passphrase.

19. The computer program product of claim 16 , wherein the secret value comprises a numerical value.

20. A system comprising:
a network adapter;
a computer readable storage device; and
a processor, wherein the processor executes instructions to:
read a secret value from the computer readable storage device, wherein the secret value includes a numerical value having a sequence of digits;
extract a plurality of portions from the secret value, wherein a first certain portion of the secret value includes a first subsequence of digits of the sequence of digits, and wherein a second certain portion of the secret value includes a second subsequence of digits of the sequence of digits;
rank each of the plurality of portions;

determine a subset of the secret value from the ranking of the plurality of portions, wherein the subset of the secret value includes a subsequence of digits of the sequence of digits;
construct a search string from the subset;

transmit by the owner of the secret value the search string to a searcher via the network adapter, wherein the owner of the secret value is a trusted party;
receive by the owner of the secret value search results from the searcher via the network adapter; and
analyze the search results to determine that there is a match between data of the search results and data of the secret value; and
based on the match initiate a change of the secret value, and wherein a search by the searcher is performed so that knowledge of the secret value is limited to the trusted party, wherein the searcher is an untrusted party that provides to the owner additional context surrounding any search hits to facilitate ascertaining by the owner whether a search hit corresponds with an instance of the secret value, and wherein the searcher is provided by a search engine that has access to a pl

Assignees

• Globalfoundries Inc
• Globalfoundries

Inventors

• Geagan Iii John Bernard
• Ponceleon Dulce B

Classifications

• G06F21/6254

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

• G06F16/951 Primary

  Indexing; Web crawling techniques · CPC title

• G06F21/6227 Primary

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

• G06F17/30864 Primary

  Physics · mapped topic