Paper 2012/350

A Note for the Ideal Order-Preserving Encryption Object and Generalized Order-Preserving Encryption

Liangliang Xiao and I-Ling Yen

Abstract

Order-preserving encryption (OPE) preserves the order of data in their ciphertexts and, hence, allows range search on the encrypted data without needing to decrypt them. Security analysis of OPE schemes is very important because OPE is not a perfect encryption algorithm (the ciphertexts leak the ordering information of the plaintexts). Most of the existing security analysis for the OPE schemes are informal: they are either based on author-defined attacks or experiments. The authors in \cite{Bol09} initiate the cryptographic study of the OPE scheme. They define the security notion POPF-CCA to qualify the security of OPE. In POPF-CCA, the ``ideal" OPE object is defined where the encryption function is uniformly randomly selected from all order-preserving functions (generally the ``ideal" OPE object is not computationally feasible), and a (constructed) ``real" OPE scheme is secure under POPF-CCA if it is computationally indistinguishable from the ideal object. In other words, although the ``ideal" OPE object is not computationally feasible, it is used as the security goal, and a (constructed) ``real" OPE scheme is secure if it is as secure as the ``ideal" OPE object. Such approach conceives the assumption (but not clearly stated and proved) that the ``ideal" OPE object is the most secure OPE. But the correctness of the assumption is an easily ignored problem. In this paper, we investigate the security of the OPE in more depth. We first give example to show that the ``ideal" OPE object may not always be the most secure OPE. It indicates that we need to use the ``ideal" encryption object more cautiously in the security analysis of OPE. Additionally we extend the concept of OPE to generalized OPE (GOPE). Unlike OPE, the ciphertexts of GOPE may not be numbers, but GOPE still enables the comparisons on the encrypted data without needing to decrypt them. We present two GOPEs in polynomial-sized and superpolynomial-sized domains that satisfy stronger notions of security than that of the ideal OPE object, respectively.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Order-preserving encryptionrange query processingideal OPE object and generalized OPEbig jump attack and small jump attachIND-OCPA and IND-OLCPA.
Contact author(s)
xll052000 @ utdallas edu
History
2012-06-22: received
Short URL
https://ia.cr/2012/350
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/350,
      author = {Liangliang Xiao and I-Ling Yen},
      title = {A Note for the Ideal Order-Preserving Encryption Object and Generalized Order-Preserving Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2012/350},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/350}},
      url = {https://eprint.iacr.org/2012/350}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.