An Ideal-Security Protocol for Order-Preserving Encoding
Order-preserving encryption - an encryption scheme where the sort order of ciphertexts matches the sort order of the corresponding plaintexts - allows databases and other applications to process queries involving order over encrypted data efficiently. The ideal security guarantee for order-preservin...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/91476 https://orcid.org/0000-0003-0238-2703 |
| _version_ | 1811078228653113344 |
|---|---|
| author | Popa, Raluca Ada Li, Frank H. Zeldovich, Nickolai |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Popa, Raluca Ada Li, Frank H. Zeldovich, Nickolai |
| author_sort | Popa, Raluca Ada |
| collection | MIT |
| description | Order-preserving encryption - an encryption scheme where the sort order of ciphertexts matches the sort order of the corresponding plaintexts - allows databases and other applications to process queries involving order over encrypted data efficiently. The ideal security guarantee for order-preserving encryption put forth in the literature is for the ciphertexts to reveal no information about the plaintexts besides order. Even though more than a dozen schemes were proposed, all these schemes leak more information than order. This paper presents the first order-preserving scheme that achieves ideal security. Our main technique is mutable ciphertexts, meaning that over time, the ciphertexts for a small number of plaintext values change, and we prove that mutable ciphertexts are needed for ideal security. Our resulting protocol is interactive, with a small number of interactions. We implemented our scheme and evaluated it on microbenchmarks and in the context of an encrypted MySQL database application. We show that in addition to providing ideal security, our scheme achieves 1 - 2 orders of magnitude higher performance than the state-of-the-art order-preserving encryption scheme, which is less secure than our scheme. |
| first_indexed | 2024-09-23T10:56:08Z |
| format | Article |
| id | mit-1721.1/91476 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:56:08Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/914762022-10-01T00:02:00Z An Ideal-Security Protocol for Order-Preserving Encoding Popa, Raluca Ada Li, Frank H. Zeldovich, Nickolai Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Popa, Raluca Ada Li, Frank H. Zeldovich, Nickolai Order-preserving encryption - an encryption scheme where the sort order of ciphertexts matches the sort order of the corresponding plaintexts - allows databases and other applications to process queries involving order over encrypted data efficiently. The ideal security guarantee for order-preserving encryption put forth in the literature is for the ciphertexts to reveal no information about the plaintexts besides order. Even though more than a dozen schemes were proposed, all these schemes leak more information than order. This paper presents the first order-preserving scheme that achieves ideal security. Our main technique is mutable ciphertexts, meaning that over time, the ciphertexts for a small number of plaintext values change, and we prove that mutable ciphertexts are needed for ideal security. Our resulting protocol is interactive, with a small number of interactions. We implemented our scheme and evaluated it on microbenchmarks and in the context of an encrypted MySQL database application. We show that in addition to providing ideal security, our scheme achieves 1 - 2 orders of magnitude higher performance than the state-of-the-art order-preserving encryption scheme, which is less secure than our scheme. Google (Firm) National Science Foundation (U.S.) (NSF award IIS-1065219) 2014-11-06T19:05:56Z 2014-11-06T19:05:56Z 2013-05 Article http://purl.org/eprint/type/ConferencePaper 978-0-7695-4977-4 978-1-4673-6166-8 978-0-7695-4977-4 INSPEC Accession Number: 13597246 http://hdl.handle.net/1721.1/91476 Popa, Raluca Ada, Frank H. Li, and Nickolai Zeldovich. “An Ideal-Security Protocol for Order-Preserving Encoding.” 2013 IEEE Symposium on Security and Privacy (May 2013), 19-22 May 2013, Berkeley, CA. p. 463-477. https://orcid.org/0000-0003-0238-2703 en_US http://dx.doi.org/10.1109/SP.2013.38 2013 IEEE Symposium on Security and Privacy Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Popa, Raluca Ada Li, Frank H. Zeldovich, Nickolai An Ideal-Security Protocol for Order-Preserving Encoding |
| title | An Ideal-Security Protocol for Order-Preserving Encoding |
| title_full | An Ideal-Security Protocol for Order-Preserving Encoding |
| title_fullStr | An Ideal-Security Protocol for Order-Preserving Encoding |
| title_full_unstemmed | An Ideal-Security Protocol for Order-Preserving Encoding |
| title_short | An Ideal-Security Protocol for Order-Preserving Encoding |
| title_sort | ideal security protocol for order preserving encoding |
| url | http://hdl.handle.net/1721.1/91476 https://orcid.org/0000-0003-0238-2703 |
| work_keys_str_mv | AT poparalucaada anidealsecurityprotocolfororderpreservingencoding AT lifrankh anidealsecurityprotocolfororderpreservingencoding AT zeldovichnickolai anidealsecurityprotocolfororderpreservingencoding AT poparalucaada idealsecurityprotocolfororderpreservingencoding AT lifrankh idealsecurityprotocolfororderpreservingencoding AT zeldovichnickolai idealsecurityprotocolfororderpreservingencoding |