System and method for fast querying of encrypted databases
AssigneeInternational Business Machines Corporation
InventorsRakesh Agrawal, Gerald George Kiernan
Life of this patent
Estimating the term…
Abstract
A system, method, computer program product, and data management service that allows any comparison operation to be applied on encrypted data, without first decrypting the operands. The encryption scheme of the invention allows equality and range queries as well as the aggregation operations of MAX, MIN, and COUNT. The GROUPBY and ORDERBY operations can also be directly applied. Query results produced using the invention are sound and complete, the invention is robust against cryptanalysis, and its security strictly relies on the choice of a private key. Order-preserving encryption allows standard database indexes to be built over encrypted tables. The invention can easily be integrated with existing systems.
Claims22
A non-transitory computer program product for automatically querying encrypted data, comprising:
- a storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising:
- partitioning plaintexts into a number of segments, wherein each plaintext comprises a plurality of values, wherein a length of each segment is selected from a range of values by calling a cryptographically secure pseudorandom number generator at least one time;
- encrypting each plaintext in an order-preserving segmented manner, yielding a corresponding ciphertext for each plaintext, wherein each ciphertext comprises values associate with each corresponding ciphertext;
- performing comparison queries on the values of the ciphertexts;
- and
- decrypting query results.
A general purpose computer system for automatically querying encrypted data, the general purpose computer system comprising:
- a memory;
- and
- a processor communicatively coupled to the memory, the processor adapted to perform a method comprising:
- partitioning plaintexts into a number of segments, wherein each plaintext comprises a plurality of values, wherein a length of each segment is selected from a range of values by calling a cryptographically secure pseudorandom number generator at least one time;
- encrypting each plaintext in an order-preserving segmented manner, yielding a corresponding ciphertext for each plaintext, wherein each ciphertext comprises values associate with each corresponding ciphertext;
- performing comparison queries on the values of the ciphertexts;
- and
- decrypting query results.
A data management service for automatically querying encrypted data, comprising:
- performing on a processor within an information processing system the following:
- partitioning plaintexts into a number of segments, wherein each plaintext comprises a plurality of values, wherein a length of each segment is selected from a range of values by calling a cryptographically secure pseudorandom number generator at least one time;
- encrypting each plaintext in an order-preserving segmented manner, yielding a corresponding ciphertext for each plaintext, wherein each ciphertext comprises values associated with each corresponding ciphertext;
- performing comparison queries on the values of the ciphertexts;
- and
- decrypting query results.
A method for automatically querying encrypted data, comprising:
- performing on a processor at an information processing system the following:
- partitioning plaintexts into a number of segments, wherein each plaintext comprises a plurality of values, wherein a length of each segment is selected from a range of values by calling a cryptographically secure pseudorandom number generator at least one time;
- encrypting each plaintext in an order-preserving segmented manner, yielding a corresponding ciphertext for each plaintext, wherein each ciphertext comprises values associated with each corresponding ciphertext;
- performing comparison queries on the values of the ciphertexts;
- and
- decrypting query results.
Dependencies are inferred from the claim text.