What Else is Revealed by Order-Revealing Encryption?
Authors:
Open Access
- 24 October 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 2016, 1155-1166
Abstract
The security of order-revealing encryption (ORE) has been unclear since its invention. Dataset characteristics for which ORE is especially insecure have been identified, such as small message spaces and low-entropy distributions. On the other hand, properties like one-wayness on uniformly-distributed datasets have been proved for ORE constructions. This work shows that more plaintext information can be extracted from ORE ciphertexts than was previously thought. We identify two issues: First, we show that when multiple columns of correlated data are encrypted with ORE, attacks can use the encrypted columns together to reveal more information than prior attacks could extract from the columns individually. Second, we apply known attacks, and develop new attacks, to show that the leakage of concrete ORE schemes on non-uniform data leads to more accurate plaintext recovery than is suggested by the security theorems which only dealt with uniform inputs.Keywords
Funding Information
- National Science Foundation (1453132)
- Defense Advanced Research Projects Agency (N66001-15-C-4070)
- Space and Naval Warfare Systems Command (N66001-15-C-4070)
This publication has 10 references indexed in Scilit:
- Practical Order-Revealing Encryption with Limited Leakage2016
- Frequency-Hiding Order-Preserving Encryption2015
- Inference Attacks on Property-Preserving Encrypted Databases2015
- Modular Order-Preserving Encryption, Revisited2015
- Semantically Secure Order-Revealing Encryption: Multi-input Functional Encryption Without Obfuscation2015
- Optimal Average-Complexity Ideal-Security Order-Preserving Encryption2014
- An Ideal-Security Protocol for Order-Preserving Encoding2013
- CryptDB2011
- Order-Preserving Symmetric Encryption2009
- Order preserving encryption for numeric data2004