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.