Average-complexity ideal-security order-preserving encryption
View Patent ↗Embodiments provide ideal security, order-preserving encryption (OPE) of data of average complexity, thereby allowing processing of the encrypted data (e.g. at a database server in response to received queries). Particular embodiments achieve high encryption efficiency by processing plaintext in the order preserved by an existing compression dictionary already available to a database. Encryption is based upon use of a binary search tree of n nodes, to construct an order-preserving encryption scheme having Ω(n) complexity and even O(n), in the average case. A probability of computationally intensive updating (which renders conventional OPE impractical for ideal security) is substantially reduced by leveraging the demonstrated tendency of a height of the binary search tree to be tightly centered around O(log n). An embodiment utilizing such an encryption scheme is described in the context of a column-store, in-memory database architecture comprising n elements. OPE according to embodiments is compatible with adjustable encryption approaches.
1. A computer-implemented method comprising:
causing an engine on a client, to create a dictionary copy preserving an order of data stored in a database on a server;
causing the engine to execute an algorithm encrypting the data on the dictionary copy according to the order;
causing the engine to update the data stored in the database according to an update probability;
causing the engine to create further encrypted data from the encrypted data;
causing the engine to send the further encrypted data to the server; and
causing the engine to send a cryptographic key to allow decryption of the further encrypted data.
2. The computer-implemented method of claim 1 wherein the algorithm comprises constructing a binary search tree comprising n nodes.
3. The computer-implemented method of claim 2 wherein the algorithm further comprises adding a buffer of at least 2 log n bits to the encrypted data to reduce the update probability.
4. The computer-implemented method of claim 1 wherein the further encrypted data is created using homomorphic encryption to allow aggregation on the database.
5. The computer-implemented method of claim 1 wherein the further encrypted data is created using deterministic encryption to allow selection on the database.
6. The computer-implemented method of claim 1 wherein the database is in the structured query language (SQL).
7. The computer-implemented method of claim 1 wherein the database comprises a column-store in-memory database.
8. A non-transitory computer readable storage medium embodying a computer program for performing a method, said method comprising:
causing an engine on a client, to create a dictionary copy preserving an order of data stored in a database on a server;
causing the engine to execute an algorithm encrypting the data on the dictionary copy according to the order;
causing the engine to update the data stored in the database according to an update probability;
causing the engine to create further encrypted data from the encrypted data;
causing the engine to send the further encrypted data to the server; and
causing the engine to send a cryptographic key to allow decryption of the further encrypted data.
9. A non-transitory computer readable storage medium as in claim 8 wherein the algorithm comprises constructing a binary search tree comprising n nodes.
10. A non-transitory computer readable storage medium as in claim 9 wherein the algorithm further comprises adding a buffer of at least 2 log n bits to the encrypted data to reduce the update probability.
11. A non-transitory computer readable storage medium as in claim 8 wherein the further encrypted data is created using homomorphic encryption to allow aggregation on the database.
12. A non-transitory computer readable storage medium as in claim 8 wherein the further encrypted data is created using deterministic encryption to allow selection on the database.
13. A non-transitory computer readable storage medium as in claim 8 wherein the database is in the structured query language (SQL).
14. A non-transitory computer readable storage medium as in claim 8 wherein the database comprises a column-store in-memory database.
15. A computer system comprising:
one or more processors;
a software program, executable on said computer system, the software program configured to:
cause an engine on a client, to create a dictionary copy preserving an order of data stored in a database on a server;
cause the engine to execute an algorithm encrypting the data on the dictionary copy according to the order;
cause the engine to update the data stored in the database according to an update probability;
cause the engine to create further encrypted data from the encrypted data;
cause the engine to send the further encrypted data to the server; and
cause the engine to send a cryptographic key to allow decryption of the further encrypted data.
16. A computer system as in claim 15 wherein the algorithm comprises constructing a binary search tree comprising n nodes.
17. A computer system as in claim 16 wherein the algorithm further comprises adding a buffer of at least 2 log n bits to the encrypted data to reduce the update probability.
18. A computer system as in claim 15 wherein the further encrypted data is created using homomorphic encryption to allow aggregation on the database.
19. A computer system as in claim 15 wherein the further encrypted data is created using deterministic encryption to allow selection on the database.
20. A computer system as in claim 15 wherein the database comprises a column-store in-memory database.