Order preserving encryption method
View Patent ↗An order-preserving encryption (OPE) encryption method receives a plaintext (clear text) and generates a ciphertext (encrypted text) using a software arbitrary precision floating point libraries during initial recursive computation rounds. In response to the ciphertext space reducing to breakpoint, the OPE encryption method continues computations using a hardware floating point processor to accelerate the computation. In this manner, the OPE encryption method enables efficient order preserving encryption to enable range queries on encrypted data.
1. A method in a network intermediary for performing order-preserving encryption of an input plaintext and generating an output ciphertext where the output ciphertext preserves the sort order of the input plaintext, the method comprising:
receiving, at the network intermediary, the input plaintext from a user device to be stored on a cloud service provider;
performing, using a processor, order-preserving encryption of the input plaintext using a random order-preserving function starting at an initial ciphertext space of N number of possibilities;
performing, using the processor to call a software arbitrary precision floating point library, a binary search of the random order-preserving function for the input plaintext to reduce the initial ciphertext space to N/2 possibilities;
in response to a size of the ciphertext space being greater than a first number of possibilities, repeating the performing of the binary search of the random order-preserving function for the input plaintext using the processor to call the software arbitrary precision floating point library to continue to reduce the number of possibilities in the ciphertext space;
in response to the size of the ciphertext space being reduced to less than the first number of possibilities, switching the processor from calling the software arbitrary precision floating point library to calling a hardware fixed precision floating point processor to perform the binary search of the random order-preserving function for the input plaintext, wherein the hardware fixed precision floating point processor is configured to handle fewer number of bits of the ciphertext space at increased speed than the software arbitrary precision floating point library to speed up remaining computations to search for the input plaintext in the random order-preserving function;
in response to a domain space of the input plaintext converging, selecting an element of the ciphertext space corresponding to the converged domain space and providing the selected element as the output ciphertext, the output ciphertext being used as an encrypted text of the input plaintext; and
transmitting the encrypted text of the input plaintext from the network intermediary to the cloud service provider to store at the cloud service provider, the encrypted text preserving the sort order of the input plaintext and enabling data query of the stored encrypted data at the cloud service provider.
2. The method of claim 1 , wherein performing, using the processor, order-preserving encryption of the input plaintext using the random order-preserving function comprises:
performing, using the processor, order-preserving encryption of the input plaintext by using a hypergeometric probability distribution to recursively sample the random order-preserving function.
3. The method of claim 1 , wherein the ciphertext space being greater than or less than the first number of possibilities comprises a ciphertext space being greater than or less than 2 P possibilities and a data string being processed having greater than or less than P databits.
4. A system for performing order-preserving encryption of an input plaintext and generating an output ciphertext where the output ciphertext preserves the sort order of the input plaintext, the system comprising:
a processor configured to:
receive, at a network intermediary, the input plaintext from a user device to be stored on a cloud service provider;
perform, using a processor, order-preserving encryption of the input plaintext using a random order-preserving function starting at an initial ciphertext space of N number of possibilities;
perform, using the processor to call a software arbitrary precision floating point library, a binary search of the random order-preserving function for the input plaintext to reduce the initial ciphertext space to N/2 possibilities;
in response to a size of the ciphertext space being greater than a first number of possibilities, repeat the performing of the binary search of the random order-preserving function for the input plaintext using the processor to call the software arbitrary precision floating point library to continue to reduce the number of possibilities in the ciphertext space;
in response to the size of the ciphertext space being reduced to less than the first number of possibilities, switch the processor from calling the software arbitrary precision floating point library to calling a hardware fixed precision floating point processor to perform the binary search of the random order-preserving function for the input plaintext, wherein the hardware fixed precision floating point processor is configured to handle fewer number of bits of the ciphertext space at increased speed than the software arbitrary precision floating point library to speed up remaining computations to search for the input plaintext in the random order-preserving function;
in response to a domain space of the input plaintext converging, select an element of the ciphertext space corresponding to the converged domain space and providing the selected element as the output ciphertext, the output ciphertext being used as an encrypted text of the input plaintext; and
transmitting the encrypted text of the input plaintext from the network intermediary to the cloud service provider to store at the cloud service provider, the encrypted text preserving the sort order of the input plaintext and enabling data query of the stored encrypted data at the cloud service provider; and
a memory coupled to the processor and configured to provide the processor with instructions.
5. The system of claim 4 , wherein the processor is further configured to perform order-preserving encryption of the input plaintext by using a hypergeometric probability distribution to recursively sample the random order-preserving function.
6. The system of claim 4 , wherein the ciphertext space being greater than or less than the first number of possibilities comprises a ciphertext space being greater than or less than 2 P possibilities and a data string being processed having greater than or less than P databits.
7. A method in a network intermediary for performing order-preserving encryption of an input plaintext and generating an output ciphertext where the output ciphertext preserves the sort order of the input plaintext, the method comprising:
receiving, at the network intermediary, the input plaintext from a user device to be stored on a cloud service provider;
performing, using a processor, order-preserving encryption of the input plaintext using a random order-preserving function starting at an initial ciphertext space of N number of possibilities;
performing, using the processor to call a first software arbitrary precision floating point library, a binary search of the random order-preserving function for the input plaintext to reduce the initial ciphertext space to N/2 possibilities;
in response to a size of the ciphertext space being greater than a first number of possibilities, repeating the performing of the binary search of the random order-preserving function for the input plaintext using the processor to call the first software arbitrary precision floating point library to continue to reduce the number of possibilities in the ciphertext space;
in response to the size of the ciphertext space being reduced to less than the first number of possibilities, switching the processor from calling the first software arbitrary precision floating point library to calling a second software floating point library to perform the binary search of the random order-preserving function for the input plaintext to continue to reduce the number of possibilities in the ciphertext space, wherein the second software floating point library has less precision than the first software arbitrary precision floating point library;
in response to a size of the ciphertext space being less than the first number of possibilities and greater than a second number of possibilities, the second number of possibilities being less than the first number of possibilities, repeating the performing of the binary search of the random order-preserving function for the input plaintext using the processor to call the second software floating point library to continue to reduce the number of possibilities in the ciphertext space;
in response to the size of the ciphertext space being reduced to less than the second number of possibilities, switching the processor from calling the second software floating point library to calling a hardware fixed precision floating point processor to perform the binary search of the random order-preserving function for the input plaintext, wherein the hardware fixed precision floating point processor is configured to handle fewer number of bits of the ciphertext space at increased speed than the first and second software floating point libraries to speed up remaining computations to search for the input plaintext in the random order-preserving function;
in response to a domain space of the input plaintext converging, selecting an element of the ciphertext space corresponding to the converged domain space and providing the selected element as the output ciphertext, the output ciphertext being the encrypted text of the input plaintext, the output ciphertext being used as an encrypted text of the input plaintext; and
transmitting the encrypted text of the input plaintext from the network intermediary to the cloud service provider to store at the cloud service provider, the encrypted text preserving the sort order of the input plaintext and enabling data query of the stored encrypted data at the cloud service provider.
8. The method of claim 7 , wherein performing, using the processor, order-preserving encryption of the input plaintext using the random order-preserving function comprises:
performing, using the processor, order-preserving encryption of the input plaintext by using a hypergeometric probability distribution to recursively sample the random order-preserving function.
9. The method of claim 7 , wherein the ciphertext space being greater than or less than the first number of possibilities comprises a ciphertext space being greater than or less than 2 P possibilities and a data string being processed having greater than or less than P databits.
10. The method of claim 9 , wherein the ciphertext space being greater than or less than the second number of possibilities comprises a ciphertext space being greater than or less than 2 P2 possibilities and a data string being processed having greater than or less than P2 databits.
11. The method of claim 7 , wherein the second software floating point library comprises a software arbitrary precision floating point library.
12. The method of claim 7 , wherein the second software floating point library comprises a software fixed precision floating point library.