Order-Preserving Encryption Secure Beyond One-Wayness.
Tal Malkin, Isamu Teranishi, Moti M. Yung · 2013
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 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.