Order-preserving encryption using approximate common divisors

James Dyer, Martin Dyer, Karim Djemame

Research output: Contribution to journalArticle

Abstract

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.

LanguageEnglish
Article number102391
JournalJournal of Information Security and Applications
Volume49
Early online date25 Sep 2019
DOIs
Publication statusE-pub ahead of print - 25 Sep 2019

Fingerprint

Cryptography
Polynomials
Distributed computer systems
Hardness

Cite this

@article{4c1579762cf24aa1a76f61f1e9694bb3,
title = "Order-preserving encryption using approximate common divisors",
abstract = "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{\^a}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.",
keywords = "Approximate common divisors, Order-preserving encryption, Secure distributed computing, Symmetric cipher",
author = "James Dyer and Martin Dyer and Karim Djemame",
year = "2019",
month = "9",
day = "25",
doi = "10.1016/j.jisa.2019.102391",
language = "English",
volume = "49",
journal = "Journal of Information Security and Applications",
issn = "2214-2126",
publisher = "Elsevier Limited",

}

Order-preserving encryption using approximate common divisors. / Dyer, James; Dyer, Martin; Djemame, Karim.

In: Journal of Information Security and Applications, Vol. 49, 102391, 01.12.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Order-preserving encryption using approximate common divisors

AU - Dyer, James

AU - Dyer, Martin

AU - Djemame, Karim

PY - 2019/9/25

Y1 - 2019/9/25

N2 - 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.

AB - 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.

KW - Approximate common divisors

KW - Order-preserving encryption

KW - Secure distributed computing

KW - Symmetric cipher

UR - http://www.scopus.com/inward/record.url?scp=85072584811&partnerID=8YFLogxK

U2 - 10.1016/j.jisa.2019.102391

DO - 10.1016/j.jisa.2019.102391

M3 - Article

VL - 49

JO - Journal of Information Security and Applications

T2 - Journal of Information Security and Applications

JF - Journal of Information Security and Applications

SN - 2214-2126

M1 - 102391

ER -