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

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 [4] initiates 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