Order-Preserving Encryption Using Approximate Integer Common Divisors

James Dyer, Martin Dyer, Jie Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

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.

LanguageEnglish
Title of host publicationData Privacy Management, Cryptocurrencies and Blockchain Technology
Subtitle of host publicationESORICS 2017 International Workshops, DPM 2017 and CBT 2017, Oslo, Norway, September 14-15, 2017, Proceedings
EditorsJoaquin Garcia-Alfaro, Guillermo Navarro-Arribas, Hannes Hartenstein, Jordi Herrera-Joancomartí
PublisherSpringer Verlag
Pages257-274
Number of pages18
ISBN (Electronic)9783319678160
ISBN (Print)9783319678153
DOIs
Publication statusPublished - 13 Sep 2017
Externally publishedYes
Event12th International Workshop on Data Privacy Management, DPM 2017 held in conjunction with 22nd European Symposium on Research in Computer Security, ESORICS 2017 and 1st International Workshop on Cryptocurrencies and Blockchain Technology, CBT 2017 - Oslo, Norway
Duration: 14 Sep 201715 Sep 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10436 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Workshop on Data Privacy Management, DPM 2017 held in conjunction with 22nd European Symposium on Research in Computer Security, ESORICS 2017 and 1st International Workshop on Cryptocurrencies and Blockchain Technology, CBT 2017
CountryNorway
CityOslo
Period14/09/1715/09/17

Fingerprint

Common divisor
Encryption
Cryptography
Integer
Leakage
Hardness
Execution Time
Game
First-order
Evaluation
Demonstrate

Cite this

Dyer, J., Dyer, M., & Xu, J. (2017). Order-Preserving Encryption Using Approximate Integer Common Divisors. In J. Garcia-Alfaro, G. Navarro-Arribas, H. Hartenstein, & J. Herrera-Joancomartí (Eds.), Data Privacy Management, Cryptocurrencies and Blockchain Technology: ESORICS 2017 International Workshops, DPM 2017 and CBT 2017, Oslo, Norway, September 14-15, 2017, Proceedings (pp. 257-274). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10436 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-67816-0_15
Dyer, James ; Dyer, Martin ; Xu, Jie. / Order-Preserving Encryption Using Approximate Integer Common Divisors. Data Privacy Management, Cryptocurrencies and Blockchain Technology: ESORICS 2017 International Workshops, DPM 2017 and CBT 2017, Oslo, Norway, September 14-15, 2017, Proceedings. editor / Joaquin Garcia-Alfaro ; Guillermo Navarro-Arribas ; Hannes Hartenstein ; Jordi Herrera-Joancomartí. Springer Verlag, 2017. pp. 257-274 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{7d5f5bfd942149a094188e99bb94f80d,
title = "Order-Preserving Encryption Using Approximate Integer Common Divisors",
abstract = "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.",
keywords = "Cloud computing, Data analytics, Order-preserving encryption, Symmetric cryptography",
author = "James Dyer and Martin Dyer and Jie Xu",
year = "2017",
month = "9",
day = "13",
doi = "10.1007/978-3-319-67816-0_15",
language = "English",
isbn = "9783319678153",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "257--274",
editor = "Joaquin Garcia-Alfaro and Guillermo Navarro-Arribas and Hannes Hartenstein and Jordi Herrera-Joancomart{\'i}",
booktitle = "Data Privacy Management, Cryptocurrencies and Blockchain Technology",

}

Dyer, J, Dyer, M & Xu, J 2017, Order-Preserving Encryption Using Approximate Integer Common Divisors. in J Garcia-Alfaro, G Navarro-Arribas, H Hartenstein & J Herrera-Joancomartí (eds), Data Privacy Management, Cryptocurrencies and Blockchain Technology: ESORICS 2017 International Workshops, DPM 2017 and CBT 2017, Oslo, Norway, September 14-15, 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10436 LNCS, Springer Verlag, pp. 257-274, 12th International Workshop on Data Privacy Management, DPM 2017 held in conjunction with 22nd European Symposium on Research in Computer Security, ESORICS 2017 and 1st International Workshop on Cryptocurrencies and Blockchain Technology, CBT 2017, Oslo, Norway, 14/09/17. https://doi.org/10.1007/978-3-319-67816-0_15

Order-Preserving Encryption Using Approximate Integer Common Divisors. / Dyer, James; Dyer, Martin; Xu, Jie.

Data Privacy Management, Cryptocurrencies and Blockchain Technology: ESORICS 2017 International Workshops, DPM 2017 and CBT 2017, Oslo, Norway, September 14-15, 2017, Proceedings. ed. / Joaquin Garcia-Alfaro; Guillermo Navarro-Arribas; Hannes Hartenstein; Jordi Herrera-Joancomartí. Springer Verlag, 2017. p. 257-274 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10436 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Order-Preserving Encryption Using Approximate Integer Common Divisors

AU - Dyer, James

AU - Dyer, Martin

AU - Xu, Jie

PY - 2017/9/13

Y1 - 2017/9/13

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

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

KW - Cloud computing

KW - Data analytics

KW - Order-preserving encryption

KW - Symmetric cryptography

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

U2 - 10.1007/978-3-319-67816-0_15

DO - 10.1007/978-3-319-67816-0_15

M3 - Conference contribution

SN - 9783319678153

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 257

EP - 274

BT - Data Privacy Management, Cryptocurrencies and Blockchain Technology

A2 - Garcia-Alfaro, Joaquin

A2 - Navarro-Arribas, Guillermo

A2 - Hartenstein, Hannes

A2 - Herrera-Joancomartí, Jordi

PB - Springer Verlag

ER -

Dyer J, Dyer M, Xu J. Order-Preserving Encryption Using Approximate Integer Common Divisors. In Garcia-Alfaro J, Navarro-Arribas G, Hartenstein H, Herrera-Joancomartí J, editors, Data Privacy Management, Cryptocurrencies and Blockchain Technology: ESORICS 2017 International Workshops, DPM 2017 and CBT 2017, Oslo, Norway, September 14-15, 2017, Proceedings. Springer Verlag. 2017. p. 257-274. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-67816-0_15