Journal
2017 IEEE SYMPOSIUM ON SECURITY AND PRIVACY (SP)
Volume -, Issue -, Pages 655-672Publisher
IEEE
DOI: 10.1109/SP.2017.44
Keywords
-
Categories
Funding
- NSF [CNS-1330308, CNS-1514163]
- Google PhD fellowship
- Sohaib and Sara Abbasi fellowship
- Division Of Computer and Network Systems
- Direct For Computer & Info Scie & Enginr [1330308, 1514163] Funding Source: National Science Foundation
Ask authors/readers for more resources
Order-preserving encryption and its generalization order-revealing encryption (OPE/ORE) allow sorting, performing range queries, and filtering data - all while only having access to ciphertexts. But OPE and ORE ciphertexts necessarily leak information about plaintexts, and what level of security they provide in practice has been unclear. In this work, we introduce new leakage-abuse attacks that recover plaintexts from OPE/ORE-encrypted databases. Underlying our new attacks is a framework in which we cast the adversary's challenge as a non-crossing bipartite matching problem. This allows easy tailoring of attacks to a specific scheme's leakage profile. In a case study of customer records, we show attacks that recover 99% of first names, 97% of last names, and 90% of birthdates held in a database, despite all values being encrypted with the OPE scheme most widely used in practice. We also show the first attack against the recent frequency-hiding Kerschbaum scheme, to which no prior attacks have been demonstrated. Our attack recovers frequently occurring plaintexts most of the time.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available