You are looking at a specific version 20130625:155230 of this paper. See the latest version.

Paper 2013/409

Order-Preserving Encryption Secure Beyond One-Wayness

Tal Malkin and Isamu Teranishi and Moti Yung

Abstract

Semantic-security of individual bits under a ciphertext are fundamental notion in modern cryptography. In this work we present the first results about this fundamental problem for Order-Preserving Encryption (OPE): ``what plaintext information can be semantically hidden by OPE encryptions?'' While OPE has gained much attention in recent years due to its usefulness in secure databases, any partial-plaintext indistinguishability (semantic security) result for it was open. Here, we propose a new indistinguishability-based security notion for OPE, which can ensure \emph{secrecy of lower bits of a plaintext} (under essentially a random ciphertext probing setting). We then propose a new scheme satisfying this security notion (while earlier schemes do not satisfy it!). We note that the known security notions tell us nothing about the above partial- plaintext indistinguishability because they are limited to being one-way-based. In addition, we show that our security notion with specific parameters implies the known security notion called WOW, and further, our scheme achieves WOW with better parameters than earlier schemes.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Order-preserving encryptionsecure encryptionsecurity notionsindistinguishabilityone-wayfoundations
Contact author(s)
teranisi @ ah jp nec com
History
2013-06-25: received
Short URL
https://ia.cr/2013/409
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.