research-article

Beyond the ideal object: towards disclosure-resilient order-preserving encryption schemes

Authors:

Guenter SchaeferAuthors Info & Claims

CCSW '13: Proceedings of the 2013 ACM workshop on Cloud computing security workshop

Pages 89 - 100

https://doi.org/10.1145/2517488.2517496

Published: 08 November 2013 Publication History

Get Access

Abstract

With the emergence of affordable cloud services, users are currently moving data to external services providers. Hence, they implicitly trust providers to not abuse or "lose" sensitive data. To protect this data in the context of cloud computing, the use of Order-Preserving Encryption (OPE) has been suggested to encrypt data while still allowing efficient queries. The reference approach builds on Order-Preserving Functions (OPFs) drawn uniformly at random: the so-called "ideal object". However, recent results question the suitability of this construction, as its security properties turn out to be poor. In this article, we investigate possible alternatives. For this, we introduce two descriptive metrics rating one-wayness-related properties of OPF construction schemes, i.e., the ability of an adversary to estimate the plaintext when given a ciphertext and possible extra information. Furthermore, we propose three novel approaches to draw OPFs and apply the introduced metrics to study their security features in relation to the "ideal object". The results visualize the extent of insecurity caused by using the "ideal object" and qualify the suitability of the alternative schemes under different threat scenarios.

References

[1]

R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu. Order Preserving Encryption for Numeric Data. In ACM SIGMOD, pages 563--574, 2004.

Digital Library

Google Scholar

[2]

G. Bebek. Anti-Tamper Database Research: Interference Control Techniques. Technical report, EECS 433 Final Report, Case Western Reserve University, 2002.

Google Scholar

[3]

A. Boldyreva, N. Chenette, Y. Lee, and A. O'Neill. Order-Preserving Symmetric Encryption. In Advances in Cryptology -- EUROCRYPT 2009, pages 224--241. 2009.

Digital Library

Google Scholar

[4]

A. Boldyreva, N. Chenette, and A. O'Neill. Order-Preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions. In Advances in Cryptology -- CRYPTO 2011, pages 578--595, 2011.

Digital Library

Google Scholar

[5]

H. Hacigumus, B. Iyer, C. Li, and S. Mehrotra. Executing SQL over Encrypted Data in the Database-Service-Provider Model. In ACM SIGMOD, pages 216--227, 2002.

Digital Library

Google Scholar

[6]

B. Hore, S. Mehrotra, M. Canim, and M. Kantarcioglu. Secure Multidimensional Range Queries over Outsourced Data. The VLDB Journal, 21(3):333--358, 2012.

Digital Library

Google Scholar

[7]

T. Malkin, I. Teranishi, and M. Yung. Order-Preserving Encryption Secure Beyond One-Wayness. Cryptology ePrint Archive, Report 2013/409, 2013.

Google Scholar

[8]

M. Matsumoto and T. Nishimura. Mersenne Twister: A 623-dimensionally Equidistributed Uniform Pseudo-Random Number Generator. ACM Transactions on Modeling and Computer Simulation (TOMACS), 8(1):3--30, 1998.

Digital Library

Google Scholar

[9]

G. Ozsoyoglu, D. Singer, and S. S. Chung. Anti-Tamper Databases: Querying Encrypted Databases. In IFIP WG 11.3 Working Conference on Database and Applications Security, volume 11, pages 4--6, 2003.

Google Scholar

[10]

R. A. Popa, F. H. Li, and N. Zeldovich. An Ideal-Security Protocol for Order-Preserving Encoding. In IEEE Symposium on Security and Privacy, pages 463--477, 2013.

Digital Library

Google Scholar

[11]

L. Xiao and I.-L. Yen. Security Analysis for Order Preserving Encryption Schemes. In Information Sciences and Systems (CISS), pages 1--6, 2012.

Google Scholar

[12]

L. Xiao, I.-L. Yen, and D. Huynh. A Note for the Ideal Order-Preserving Encryption Object and Generalized Order-Preserving Encryption. Cryptology ePrint Archive, Report 2012/350, 2012.

Google Scholar

Cited By

View all

Shen NYeh JSun HChen C(2021)A Practical and Secure Stateless Order Preserving Encryption for Outsourced Databases2021 IEEE 26th Pacific Rim International Symposium on Dependable Computing (PRDC)10.1109/PRDC53464.2021.00025(133-142)Online publication date: Dec-2021
https://doi.org/10.1109/PRDC53464.2021.00025
Bogatov DKollios GReyzin L(2019)A comparative evaluation of order-revealing encryption schemes and secure range-query protocolsProceedings of the VLDB Endowment10.14778/3324301.332430912:8(933-947)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.14778/3324301.3324309
Waage TWiese L(2018)CloudDBGuard: Enabling Sorting and Searching on Encrypted Data in NoSQL Cloud DatabasesBig Data Analytics and Knowledge Discovery10.1007/978-3-319-98539-8_20(261-270)Online publication date: 8-Aug-2018
https://doi.org/10.1007/978-3-319-98539-8_20
Show More Cited By

Index Terms

Beyond the ideal object: towards disclosure-resilient order-preserving encryption schemes

Recommendations

Frequency-Hiding Order-Preserving Encryption
CCS '15: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security

Order-preserving encryption allows encrypting data, while still enabling efficient range queries on the encrypted data. This makes its performance and functionality very suitable for data outsourcing in cloud computing scenarios, but the security of ...
Optimal Average-Complexity Ideal-Security Order-Preserving Encryption
CCS '14: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security

Order-preserving encryption enables performing many classes of queries -- including range queries -- on encrypted databases. Popa et al. recently presented an ideal-secure order-preserving encryption (or encoding) scheme, but their cost of insertions (...
On the Security of a Modified Paillier Public-Key Primitive
ACISP '02: Proceedings of the 7th Australian Conference on Information Security and Privacy

Choi et al. proposed the modified Paillier cryptosystem (M-Paillier cryptosystem). They use a special public-key g ZZ/nZZ such that g ^{( n )} = 1+ n mod n ², where n is the RSA modulus. The distribution of the public key g is different ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CCSW '13: Proceedings of the 2013 ACM workshop on Cloud computing security workshop

November 2013

132 pages

ISBN:9781450324908

DOI:10.1145/2517488

Program Chairs:
Ari Juels
RSA Laboratories, USA
,
Bryan Parno
Microsoft Research, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 November 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS'13

Sponsor:

SIGSAC

CCS'13: 2013 ACM SIGSAC Conference on Computer and Communications Security

November 8, 2013

Berlin, Germany

Acceptance Rates

CCSW '13 Paper Acceptance Rate 11 of 28 submissions, 39%;

Overall Acceptance Rate 37 of 108 submissions, 34%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
218
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Shen NYeh JSun HChen C(2021)A Practical and Secure Stateless Order Preserving Encryption for Outsourced Databases2021 IEEE 26th Pacific Rim International Symposium on Dependable Computing (PRDC)10.1109/PRDC53464.2021.00025(133-142)Online publication date: Dec-2021
https://doi.org/10.1109/PRDC53464.2021.00025
Bogatov DKollios GReyzin L(2019)A comparative evaluation of order-revealing encryption schemes and secure range-query protocolsProceedings of the VLDB Endowment10.14778/3324301.332430912:8(933-947)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.14778/3324301.3324309
Waage TWiese L(2018)CloudDBGuard: Enabling Sorting and Searching on Encrypted Data in NoSQL Cloud DatabasesBig Data Analytics and Knowledge Discovery10.1007/978-3-319-98539-8_20(261-270)Online publication date: 8-Aug-2018
https://doi.org/10.1007/978-3-319-98539-8_20
Waage TWiese L(2017)Property Preserving Encryption in NoSQL Wide Column StoresOn the Move to Meaningful Internet Systems. OTM 2017 Conferences10.1007/978-3-319-69459-7_1(3-21)Online publication date: 21-Oct-2017
https://doi.org/10.1007/978-3-319-69459-7_1
Yang CZhang WDing JYu N(2017)Probability-p Order-Preserving EncryptionCloud Computing and Security10.1007/978-3-319-68542-7_2(16-28)Online publication date: 2-Nov-2017
https://doi.org/10.1007/978-3-319-68542-7_2
Kerschbaum FRay ILi NKruegel C(2015)Frequency-Hiding Order-Preserving EncryptionProceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security10.1145/2810103.2813629(656-667)Online publication date: 12-Oct-2015
https://dl.acm.org/doi/10.1145/2810103.2813629
Sanamrad TBraun LKossmann DVenkatesan R(2014)Randomly Partitioned Encryption for Cloud DatabasesProceedings of the 28th Annual IFIP WG 11.3 Working Conference on Data and Applications Security and Privacy XXVIII - Volume 856610.1007/978-3-662-43936-4_20(307-323)Online publication date: 14-Jul-2014
https://dl.acm.org/doi/10.1007/978-3-662-43936-4_20

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Frequency-Hiding Order-Preserving Encryption

Optimal Average-Complexity Ideal-Security Order-Preserving Encryption

On the Security of a Modified Paillier Public-Key Primitive