Secure matching supporting fuzzy data

Patent metadata

Field	Value
Publication number	US-9652512-B2
Application number	US-201414493835-A
Country	US
Kind code	B2
Filing date	Sep 23, 2014
Priority date	Mar 13, 2013
Publication date	May 16, 2017
Grant date	May 16, 2017

Abstract

Provided are techniques for secure matching supporting fuzzy data. A first bloom filter for a first data element is retrieved, wherein each of the characters in the data element has been encrypted with a beginning offset position of the character and encrypted with an end offset position of the character to produce two encrypted values that are added to the first bloom filter. A second bloom filter for a second data element is retrieved. The first bloom filter and the second bloom filter are compared to determine whether there is a match between the first data element and the second data element.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
creating, using a processor of a computer, a first bloom filter for a first data element, wherein the first bloom filter includes an array with two encrypted values for each of multiple characters of the first data element, by encrypting each character of the multiple characters of the first data element with a beginning offset position to generate a first value of the two encrypted values and with an end offset position to generate a second value of the two encrypted values;
creating, using the processor of the computer, a second bloom filter for a second data element, wherein the second bloom filter includes another array with two encrypted values for each of multiple characters of the second data element, by encrypting each character of the multiple characters of the second data element with a beginning offset position to generate a first value of the two encrypted values and with an end offset position to generate a second value of the two encrypted values;
receiving, using the processor of the computer, a query with the first bloom filter, the second bloom filter, and a logical operation that indicates how the first bloom filter and the second bloom filter are combined;
using fuzzy matching to compare, using the processor of the computer, the first bloom filter and the second bloom filter with the logical operation against data elements in a data store to determine whether there is a match to at least one of the data elements; and
in response to determining that there is a match to at least one of the data elements, returning, using the processor of the computer, an indication that there is a match; and
in response to determining that there is no match to at least one of the data elements, returning, using the processor of the computer, an indication that there is no match.

2. The method of claim 1 , wherein the beginning offset position that is a first shared secret is randomly generated.

3. The method of claim 1 , wherein the end offset position of the character that is a second shared secret is randomly generated.

4. The method of claim 1 , wherein the logical operation comprises a combination of AND and OR operators.

5. The method of claim 1 , wherein a Software as a Service (SaaS) is provided to perform method operations.

Assignees

• IBM

Inventors

• Litherland Michael B
• Milman Ivan M
• Oberhofer Martin
• Padilla Donald A

Classifications

• G06F21/602

  Providing cryptographic facilities or services · CPC title

• G06F16/2468 Primary

  Fuzzy queries · CPC title

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F17/30312

  Physics · mapped topic

• G06F17/30542 Primary

  Physics · mapped topic