Order-preserving encryption using the hypergeomatric probability distribution leaks about the half bits of a plaintext and the distance between two arbitrary plaintexts. To solve these problems, Popa et al. proposed a mutable order-preserving encoding. This is a keyless encoding scheme that adopts an order-preserving index locating the corresponding ciphertext via tree-based data structures. Unfortunately, it has the following shortcomings. First, the frequency of the ciphertexts reveals that of the plaintexts. Second, the indices are highly correlated to the corresponding plaintexts. For these reasons, statistical cryptanalysis may identify the encrypted fields using public information. To overcome these limitations, we propose a multi-tree approach to the mutable order-preserving encoding. The cost of interactions increases by the increased number of trees, but the proposed scheme mitigates the distribution leakage of plaintexts and also reduces the problematic correlation to plaintexts.

In this letter, we propose a secrecy criterion for outsourcing encrypted databases. In encrypted databases, encryption schemes revealing some information are often used in order to manipulate encrypted data efficiently. The proposed criterion is based on inference analysis for databases: We simulate attacker's inference on specified secret information with and without the revealed information from the encrypted database. When the two inference results are the same, then secrecy of the specified information is preserved against outsourcing the encrypted database. We also show that the proposed criterion is decidable under a practical setting.