Computing range queries over encrypted data
AssigneeInternational Business Machines Corporation
InventorsSupriyo CHAKRABORTY, Akshar KAUL, Hugo KRAWCZYK
Life of this patent
Estimating the term…
Abstract
A method (and structure and computer product) to encrypt plaintext data into ciphertext data includes encrypting, using a processor on a computer, plaintext into corresponding ciphertext, using a Property Preserving Encryption (PPE) protocol in which a predefined property is maintained when plaintext values are encrypted into ciphertext values. The predefined property is randomly flipped during encryption to reverse the predefined property in the corresponding ciphertext node. An indication of whether the predefined property has been maintained or reversed is stored as the state of encryption.
Claims20
A method to encrypt data, the method comprising:
- encrypting plaintext data into ciphertext data by executing a Property Preserving Encryption (PPE) scheme on a processor on a computer as an encryption process, the PPE scheme preserving a predefined property between plaintext values and their associated ciphertext values, wherein the encryption process randomly flips the predefined property and generates a state of encryption that comprises a record of whether the predefined property is maintained or flipped during an encryption;
- storing the ciphertext data;
- and
- storing the state of encryption as a record of when the predefined property has been randomly broken.
A method of computing range queries over encrypted data, the method comprising:
- initially encrypting plaintext data by executing an Order Preserving Encryption (OPE) protocol as an encryption on a processor on a computer and storing ciphertext data in a database via a remote, unsecured server, the OPE protocol maintaining an order of values when plaintext values are encrypted into ciphertext values, wherein during the encrypting, for each node of plaintext being encrypted, the order is randomly flipped, and, for each encrypted plaintext node, a state of encryption is generated and stored so as to record whether the order has been maintained or reversed for its corresponding ciphertext node, and wherein ciphertext values assigned to each plaintext value is stored in the database;
- receiving a query to be executed over the plaintext values from a client application;
- rewriting the received query to account for whether flipping has been assigned for nodes involved in the query, using information in the state of encryption generated during the encryption of the plaintext data;
- and
- transmitting the rewritten query to the remote, unsecured server to be executed.
A method of encrypting plaintext values, using a Flipped Order Preserving Encryption (FOPE) encryption scheme, the method comprising:
- randomly flipping an order of ciphertext values relative to their corresponding plaintext values, while also generating a state of encryption that indicates whether the order is maintained or flipped during the encryption, and storing the ciphertext values assigned to the plaintext values;
- storing the ciphertext values that correspond to the plaintext values;
- and
- storing the state of encryption as a record of when the order of the OPE scheme was broken.
Dependencies are inferred from the claim text.