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

Category / Keywords: secret-key cryptography / Order-preserving encryption; range query processing; ideal OPE object and generalized OPE; big jump attack and small jump attach; IND-OCPA and IND-OLCPA.