Cryptanalysis of Comparable Encryption in SIGMOD'16
Cryptanalysis of Comparable Encryption in SIGMOD'16
复制标题
DOI：
10.1145/3035918.3035948
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Caleb Horst;Ryo Kikuchi;Keita Xagawa
中科院分区：
文献类型：
--
作者：
Caleb Horst;Ryo Kikuchi;Keita Xagawa
Furukawa提出的可比较加密（Esorics 2013，Cans 2014）是订单保留加密的变体（OPE）和订购式加密（ore）； V的密文和B的A代币，并比较A $ B $的代币和另一个可比较的加密。最近只是可比较的加密。数据库，这意味着每个加密在数据库中都有两个位置，与两个解释相对应，除非可以检测到虚拟值，否则在数据库中掩盖了正确的位置。反对攻击的对手需要o（ℓ）o（ℓ）才能恢复秘密键，其中ℓ是一个安全参数。使用简单的线性代数加密方案。使用两个令牌订单的仅限文本攻击正确地命令 - 使用两个令牌和两个宣传的攻击。模棱两可的方案： - 使用两个令牌命令使用恒定概率的密文命令 - 使用三个令牌和三个明文揭示了V的精确值。
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 vdummy. 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(ℓ) plaintext-ciphertext pairs to recover secret key, where ℓ 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(ℓ) 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.