Order-preserving encryption using approximate common divisors

James Dyer, Martin Dyer, Karim Djemame

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


Order-preservation is a highly desirable property for encrypted databases as it allows range queries over ciphertexts. Order-preserving encryption (OPE) is used in the encrypted database systems CryptDB and Cipherbase. The former has been adopted by several commercial organisations and the latter was developed as an extension of Microsoftâs SQLServer. We present two novel, but simple, randomised OPE schemes based on the general approximate common divisor problem (GACDP) and decisional polynomial approximate common divisor problem (DPolyACDP) respectively. These appear to be the first OPE schemes to be based on a computational hardness primitive, rather than a security game. Our GACDP based scheme is very efficient, requiring only O(1) arithmetic operations for encryption and decryption. Our DPolyACDP based scheme is similarly efficient. We show that these schemes have near optimal information leakage. We demonstrate how our OPE schemes can be integrated into a secure distributed computing system which computes over encrypted data. We report on an extensive evaluation of our GACDP-based algorithms in such a scenario, a MapReduce computation over encrypted data. The results clearly demonstrate extremely favourable execution times in comparison with existing OPE schemes.

Original languageEnglish
Article number102391
Number of pages16
JournalJournal of Information Security and Applications
Early online date25 Sep 2019
Publication statusPublished - 1 Dec 2019


Dive into the research topics of 'Order-preserving encryption using approximate common divisors'. Together they form a unique fingerprint.

Cite this