Order-Preserving Encryption Using Approximate Integer Common Divisors
This work addresses the need for efficient and secure order-preserving encryption, which is crucial for applications like database queries, but it is incremental as it builds on existing OPE concepts with a new computational approach.
The paper tackles the problem of order-preserving encryption (OPE) by introducing a new scheme based on the general approximate common divisor problem (GACDP), achieving optimal information leakage for uniformly distributed plaintexts and requiring only O(1) arithmetic operations for encryption and decryption. The results demonstrate highly favorable execution times compared to existing OPE schemes.
We present a new, but simple, randomised order-preserving encryption (OPE) scheme based on the general approximate common divisor problem (GACDP). This appears to be the first OPE scheme to be based on a computational hardness primitive, rather than a security game. This scheme requires only $O(1)$ arithmetic operations for encryption and decryption. We show that the scheme has optimal information leakage under the assumption of uniformly distributed plaintexts, and we indicate that this property extends to some non-uniform distributions. We report on an extensive evaluation of our algorithms. The results clearly demonstrate highly favourable execution times in comparison with existing OPE schemes.