Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Order-preserving encryption, secure encryption, security notions, indistinguishability, one-way, foundations

Date: received 21 Jun 2013

Contact author: teranisi at ah jp nec com

Available format(s): PDF | BibTeX Citation

Version: 20130625:155230 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]