2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't think it does weaken the paillier cryptosystem. Paillier has been used in situations (e.g., voting), where the plaintext space is $\{0,1\}$. In those applications, picking two ciphertexts, you have a pretty good chance of getting two that encrypt the same message. Yet these applications remain secure. That is the best I can give you right now, however. It will be interesting to see if someone finds a paper that proves this. $\endgroup$
    – mikeazo
    Jul 7, 2015 at 12:10
  • $\begingroup$ Ok this is an interesting reference, my hunch could be wrong too. Lets see if others have any answers. Initially was trying to see if we can deduct the random values $r_1,r_2$ by knowing their ciphertexts are equal but that seems not possible $\endgroup$
    – sashank
    Jul 7, 2015 at 12:13
  • $\begingroup$ Another thought, we know that knowing two ciphertexts that encrypt the same plaintext cannot leak information about the private key as any adversary with the public key can construct such encryptions. So, the only possibilities is that it leaks information about either the message itself or the randomness values used. $\endgroup$
    – mikeazo
    Jul 7, 2015 at 13:02

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ It's quite easy to write a formal reduction to prove this as well. It's a good exercise so is recommended. $\endgroup$
    – Yehuda Lindell
    Jul 7, 2015 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.