String matching in encrypted data

1. A computing device configured to identify matching strings in electronically stored representations of encrypted data, the computing device comprising:

computer memory configured to store electronically a plurality of encrypted strings as a corresponding plurality of rows of encrypted bits in a dataset, the plurality of encrypted strings being encrypted according to a homomorphic encryption scheme;

a processor system configured to operate on the electronically stored plurality of encrypted strings to:

receive an encrypted query string encrypted according to the homomorphic encryption scheme;

compute, for each of the corresponding plurality of rows of the dataset, a sum of a function of dataset bits and query bits, to obtain a corresponding row result;

multiply one or more of the corresponding row results to obtain a product; and

upon determining that the product is zero, return an indication that the encrypted query string matches one or more of the plurality of encrypted strings of the dataset;

and operate on the electronically stored representations to apply a randomization algorithm effective to mask the homomorphic encrypted data to prevent exposure by the computed sum and the multiply operations.

2. The computing device as recited in claim 1 , wherein the processor system is further configured to operate on the electronically stored representations to:

compute for each row of the dataset, a product over a function of dataset bits and query bits to obtain a row result; and

add the row results of the computed rows to determine a total number of the one or more matching strings.

3. The computing device as recited in claim 1 , wherein the processor system is further configured to operate on the electronically stored representations to represent the dataset bits and the query bits of the encrypted query string in an integer base larger than two (2).

4. The computing device as recited in claim 1 , wherein the processor system is further configured to operate on the electronically stored representations to:

simultaneously query the dataset of the homomorphic encrypted data for multiple encrypted query strings; and

determine multiple matching strings of the multiple encrypted query strings in the dataset.

5. The computing device as recited in claim 1 , wherein the processor system is further configured to operate on the electronically stored representations to reduce a size of the encrypted query string prior to the addition and multiplication operations that provide the one or more matching strings of the encrypted query string in the dataset.

6. The computing device as recited in claim 1 , wherein the processor system is further configured to operate on the electronically stored representations to apply a hashing algorithm to organize dataset strings into bins for comparing the encrypted query string prior to the addition and multiplication operations.

7. The computing device as recited in claim 1 , wherein the processor system is further configured to operate on the electronically stored representations to apply a Galois unpacking algorithm to initiate multiple encrypted query strings in a single ciphertext.

8. Enacted in a computing device having computer memory operatively coupled to a processor system, a method for identifying matching strings in electronically stored representations of encrypted data, the method comprising:

storing electronically a plurality of encrypted strings as a corresponding plurality of rows of encrypted bits in a dataset, the plurality of encrypted strings being encrypted according to a homomorphic encryption scheme;

receiving an encrypted query string encrypted according to the homomorphic encryption scheme;

representing the dataset bits and query bits of the encrypted query string in an integer base larger than two;

applying one or more algorithms to perform addition and multiplication operations of a string matching application, wherein the addition and multiplication operations comprise:

computing for each row of the dataset, a sum of some function of dataset bits and query bits for a row result; and

multiplying the row results of the computed rows to determine one or more matching strings;

upon determining that the one or more matching strings of the encrypted query string is present in the dataset,

returning an indication of the one or more matching strings; and

applying a randomization algorithm effective to mask the homomorphic encrypted data to prevent exposure by the computing the sum and the multiplying operations.

9. The method as recited in claim 8 , further comprising:

computing for each row of the dataset, a product over a function of dataset bits and query bits for a row result; and

adding the row results of the computed rows to determine a total number of the one or more matching strings.

10. The method as recited in claim 8 , further comprising:

applying a Galois unpacking algorithm to initiate multiple encrypted query strings in a single ciphertext.

11. The method as recited in claim 8 , further comprising:

querying the dataset of the homomorphic encrypted data for multiple encrypted query strings; and

determining multiple matching strings of the multiple encrypted query strings in the dataset.

12. The method as recited in claim 8 , further comprising:

reducing a size of the encrypted query string prior to the addition and multiplication operations that provide the one or more matching strings of the encrypted query string in the dataset.

13. The method as recited in claim 8 , further comprising:

applying a hashing algorithm to organize dataset strings into bins for comparing the encrypted query string prior to the addition and multiplication operations.

14. Enacted in a computing device having computer memory operatively coupled to a processor system, a method for identifying matching strings in electronically stored representations of encrypted data, the method comprising:

storing electronically a plurality of encrypted strings as a corresponding plurality of rows of encrypted bits in a dataset, the plurality of encrypted strings being encrypted according to a homomorphic encryption scheme;

receiving an encrypted query string encrypted according to the homomorphic encryption scheme;

computing, for each of the corresponding plurality of rows of the dataset, a sum of a function of dataset bits and query bits, to obtain a corresponding a row result;

multiplying one or more of the corresponding row results to obtain a product;

upon determining that the product is zero, returning an indication that the encrypted query string matches one or more of the plurality of encrypted strings of the dataset; and

operating on the electronically stored representations to apply a randomization algorithm effective to mask the homomorphic encrypted data to prevent exposure by the computed sum and the multiply operations.

15. The method as recited in claim 14 , further comprising:

applying a hashing algorithm to organize dataset strings into bins for comparing the encrypted query string prior to the computing the sum and the multiplying to determine the one or more matching strings of the encrypted query string in the dataset.