System and method for secure database queries

Patent metadata

Field	Value
Publication number	US-9647843-B2
Application number	US-201615069616-A
Country	US
Kind code	B2
Filing date	Mar 14, 2016
Priority date	Mar 13, 2013
Publication date	May 9, 2017
Grant date	May 9, 2017

Abstract

Disclosed are a system and method of performing secure computations on a protected database. Embodiments of the method provide, in a secure processor, a database of cryptographically hashed values based on a database of cleartext values, receive a cryptographically hashed query value as input into the secure processor wherein the query value is a hash of a cleartext value that corresponds to a cleartext query, perform a comparison operation within the secure processor to determine the presence of the hashed query value within the database of cryptographically hashed values and provide the results of the comparison operation to an external interface of the secure processor, wherein the contents of the database of cryptographically hashed values and the comparison operations are encapsulated within the secure processor and unexposed externally therefrom.

First claim

What is claimed is:

1. A method of performing secure computations on a protected database comprising:
providing, in a secure processor, a database of cryptographically hashed values based on a database of cleartext values;
a non-secure processor:
receiving a cleartext query;
producing variations of the cleartext query by iteratively stripping off or substituting characters or substrings at the end of the cleartext query string based on the data type; and
hashing the cleartext query and the variations of the cleartext query to form a plurality of cryptographically hashed query values;

receiving the plurality of cryptographically hashed query values as input into the secure processor wherein the query values are a hash of a cleartext value that corresponds to a cleartext query and the variations of the cleartext query;
performing a comparison operation within the secure processor to determine the presence of any of the hashed query values within the database of cryptographically hashed values, wherein the performing a comparison operation includes:
(a) XOR'ing a least-significant bit (“LSB”) of one of the hashed query values with a LSB of a cryptographically hashed value from the database of cryptographically hashed values;
(b) XOR'ing a next LSB of one of the hashed query values with a next LSB of the cryptographically hashed value;
(c) repeating the XOR'ing of the next LSB of one of the hashed query values with the next LSB of the cryptographically hashed value through a most-significant bit (MSB) of the hashed query value and the MSB of the cryptographically hashed value; and
(d) producing a bit string of the XOR'ed bits, wherein a bit string that is a sequence of 0's indicates a match between one of the hashed query values and the cryptographically hashed value; and
providing the results of the comparison operation to an external interface of the secure processor, wherein the contents of the database of cryptographically hashed values and the comparison operation are encapsulated within the secure processor and unexposed externally therefrom.

2. The method of claim 1 wherein the performing a comparison operation further includes repeating (a)-(d) for each cryptographically hashed value in the database of cryptographically hashed values.

3. The method of claim 2 wherein the repeating (a)-(d) repeats (a)-(d) until a match between the at least one of the hashed query values and the cryptographically hashed value is found.

4. The method of claim 1 wherein the performing a comparison operation further includes outputting an integer 1 if a match between at least one of the hashed query values and the cryptographically hashed value is found.

5. The method of claim 1 wherein the performing a comparison operation further includes outputting a “true” if a match between at least one of the hashed query values and the cryptographically hashed value is found.

6. The method of claim 2 wherein the performing a comparison operation further includes outputting a “false” if no match between any of the hashed query values and the cryptographically hashed values is found.

7. The method of claim 1 wherein the non-secure processor produces the cryptographically hashed query value by transforming the cleartext query to a hashed value.

8. The method of claim 1 wherein the data type includes URLs and IP addresses and producing the variations of the cleartext query includes stripping the leftmost character from URL cleartext query strings and stripping or substituting the rightmost character(s) from IP address cleartext query strings.

9. A non-transitory computer readable medium comprising instructions for performing secure computations on a protected database, by:
providing, in a secure processor, a database of cryptographically hashed values based on a database of cleartext values;
a non-secure processor:
receiving a cleartext query;
producing variations of the cleartext query by iteratively stripping off or substituting characters or substrings at the end of the cleartext query string based on the data type; and
hashing the cleartext query and the variations of the cleartext query to form a plurality of cryptographically hashed query values;

receiving the plurality of cryptographically hashed query values as input into the secure processor wherein the query values are a hash of a cleartext value that corresponds to a cleartext query and the variations of the cleartext query;
performing a comparison operation within the secure processor to determine the presence of any of the hashed query values within the database of cryptographically hashed values, wherein the performing a comparison operation includes:
(a) XOR'ing a least-significant bit (“LSB”) of one of the hashed query values with a LSB of a cryptographically hashed value from the database of cryptographically hashed values;
(b) XOR'ing a next LSB of one of the hashed query values with a next LSB of the cryptographically hashed value;
(c) repeating the XOR'ing of the next LSB of one of the hashed query values with the next LSB of the cryptographically hashed value through a most-significant bit (MSB) of the hashed query value and the MSB of the cryptographically hashed value; and
d) producing a bit string of the XOR'ed bits, wherein a bit string that is a sequence of 0's indicates a match between one of the hashed query values and the cryptographically hashed value; and
providing the results of the comparison operation to an external interface of the secure processor, wherein the contents of the database of cryptographically hashed values and the comparison operation are encapsulated within the secure processor and unexposed externally therefrom.

10. The computer readable medium of claim 9 in which the performing a comparison operation further includes repeating (a)-(d) for each cryptographically hashed value in the database of cryptographically hashed values.

11. The computer readable medium of claim 10 wherein the repeating (a)-(d) repeats (a)-(d) until a match between at least one of the hashed query values and the cryptographically hashed value is found.

12. The computer readable medium of claim 10 in which the performing a comparison operation further includes outputting an integer 1 if a match between at least one of the hashed query values and the cryptographically hashed value is found.

13. The computer readable medium of claim 10 in which the performing a comparison operation further includes outputting a “true” if a match between at least one of the hashed query values and the cryptographically hashed value is found.

14. The computer readable medium of claim 10 in which the performing a comparison operation further includes outputting a “false” if no match any of the hashed query values and the cryptographically hashed values is found.

15. The computer readable medium of claim 10 wherein the data type includes URLs and IP addresses and producing the variations of the cleartext query includes stripping the leftmost character from URL cleartext query strings and stripping or substituting the rightmost character(s) from IP address cleartext query strings.

16. A method of performing secure computations on a protected database comprising:
providing, in a secure processor, a database of cryptographically hashed values based on a database of cleartext values;
receiving a cleartext query of the database of cryptographically hashed values;
producing variations of the cleartext query by iteratively stripping off or substituting characters or substrings at the end of the cleartext query string based on the data type;
hashin

Assignees

• Northrop Grumman Systems Corp

Inventors

• Bennison James E

Classifications

• G06F21/72 Primary

  in cryptographic circuits · CPC title

• G06F16/137

  Hash-based (content-based indexing of textual data G06F16/31) · CPC title

• G06F21/6227

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

• H04L9/3236 Primary

  using cryptographic hash functions · CPC title

• G06F17/30097

  Physics · mapped topic