Cryptography
- paillier deterministic-encryption order-preserving probabilistic-encryption cryptdb
- Updated Fri, 10 Jun 2022 14:00:52 GMT
-
Weakening of Paillier cryptosystem due to ciphertext equivalence and order in CryptDB
The Paillier cryptosystem is probabilistic in nature and IND-CPA secure. By design given two ciphertexts one cannot distinguish whether decrypting those two ciphertexts will result in same or different plaintexts.
But in certain situations like Onion-layered encryption in CryptDB. There are other onions like DET and OPE that reveal whether two ciphertexts map to same underlying plaintext or whether the plaintexts are greater or less when compared to each other.
For example , in CryptDB the plaintext is encrypted using multiple schemes and stored separately. So two different plaintexts $m_1,m_2$, assuming both are numbers, would look in the tables as below
- HOM Onion : Paillier_Enc($m_n,k_1$) = $c^h_n$ , $h$ denotes the homomorphic layer
- DET Onion : AES_Enc($m_n, k_2$) = $c^d_n$, $d$ denotes the deterministic layer
- OPE Onion : OPE_ENC($m_n, k_3$) = $c^o_n$, $o$ denotes the order preserving layer
Now although $c^h_1 , c^h_2$ do not reveal whether $m_1, m_2$ are equal because the Paillier scheme is probabilistic . There are other onion layers revealing whether the $m_1,m_2$ are same or less or greater to each other.
My hunch is these inferences from other layers weaken the Paillier cryptosystem's security guarantees, but I could not come up with a way to weaken them. So how can we take advantage of other onions leaking inferences (about equality, comparison) to break the Paillier system in some way?
Solution
Your hunch is wrong because of the definition of CPA security: Assume that some knowing some kind of relation between two plaintexts would give the attacker an advantage.
Now think of the INC-CPA game: Nothing stops the attacker from choosing exactly this kind of relationship. And if the scheme is IND-CPA secure, knowledge of such a relation does not break the scheme. As mikeazo pointed out: Even if you only use a message space of $\{0,1\}$, CPA security still ensures the attacker can not distinguish their encryptions.
The other aspect you hinted at: Under CPA security it is not possible to distinguish whether two ciphertexts encrypt the same plaintext: The attacker can encrypt $m_1$ and $m_2$ as often as he wishes. If there was a way to determine that one of the encryptions encrypts the same ciphertext as the challenge, he wins.