Cryptanalysis of Comparable Encryption in SIGMOD'16

Comparable Encryption proposed by Furukawa (ESORICS 2013, CANS 2014) is a variant of order-preserving encryption (OPE) and order-revealing encryption (ORE); we cannot compare a ciphertext of v and another ciphertext of v', but we can compare a ciphertext of v and a token of b and compare a token of b and another token of b'. Comparable encryption allows us to implement range and point queries while keeping the order of v's as secret as possible. Recently, Karras, Malhotra, Bhatt, Nikitin, Antyukhov, and Idreos independently re-define comparable encryption and propose two schemes, a basic one and an ambiguous one, based on linear algebra (SIGMOD 2016). The basic scheme is just comparable encryption. To hide the order revealed by tokens, they also proposed an ambiguous scheme where each ciphertext has two interpretations v and v(dummy). In the context of an indexed database, this means that every encryption has two places in the database corresponding to the two interpretations, masking the correct placement in the database unless the dummy value is detectable. They assessed that their basic scheme (and ambiguous scheme upon the basic scheme) is secure against known-plaintext attacks; the adversary will require O(l) plaintext-ciphertext pairs to recover secret key, where l is a security parameter. This paper cryptanalyzes their comparable encryption schemes by using simple linear algebra. We show that a few tokens and a few plaintext-ciphertext pairs instead of O(l) pairs allow us to mount several attacks efficiently. Our attacks are summarized as follows: Attacks against the basic scheme: - A ciphertext-only attack using two tokens orders the ciphertexts correctly. - A known-plaintext attack using two tokens and two plaintexts reveals exact value of v. Attacks against the ambiguous scheme: - A ciphertext-only attack using two tokens orders the ciphertexts with a constant probability. - A known-plaintext attack using three tokens and three plaintexts reveals exact value of v.