Cryptography

# 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

1. HOM Onion : Paillier_Enc($$m_n,k_1$$) = $$c^h_n$$ , $$h$$ denotes the homomorphic layer
2. DET Onion : AES_Enc($$m_n, k_2$$) = $$c^d_n$$, $$d$$ denotes the deterministic layer
3. 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.

• +1 – It's quite easy to write a formal reduction to prove this as well. It's a good exercise so is recommended. — Jul 07, 2015 at 16:02