Consider a variant of the Paillier encryption scheme where the message space is restricted to $\mathbb{Z}_q$ such that the RSA modulus $N$ of the Paillier cryptosystem satisfies $N > q + q^2$. I am interested in the following variant of the CCA security game where the decryption oracle answers with not a complete decryption of the requested ciphertext but with an integer blinding of it:

  • $\mathcal{C}: pk, sk \leftarrow \mathsf{Keygen}(1^{\lambda})$. Give $pk$ to $\mathcal{A}$.
  • $\mathcal{C}:$ Choose $b \xleftarrow{\\\$} \{0,1\}$.
  • Encryption queries:
    • $\mathcal{A}:$ Give $m_{0_i},m_{1_i} \in \mathbb{Z}_q$ to $\mathcal{C}$.
    • $\mathcal{C}:$ $c_i \leftarrow \mathsf{Enc}(pk, m_{b_i})$. Give $c_i$ to $\mathcal{A}$.
  • Blinded decryption queries:
    • $\mathcal{A}:$ Give ciphertext $c' \neq c_i$ for any $i$ to $\mathcal{C}$.
    • $\mathcal{C}:$ $m' \leftarrow \mathsf{Dec}(sk, c')$; $r \xleftarrow{\\\$} \mathbb{Z}_{q^2}$; $\tilde{m}' \leftarrow m' + r \mod N$. Give $\tilde{m}'$ to $\mathcal{A}$.
  • $\mathcal{A}:$ Output $b' \in \{0,1\}$ as its guess of $b$.

My question is whether the above notion of security holds for the above variant of the Paillier encryption scheme? Intuitively, it appears that for any ciphertext encrypting a message in the valid message space $\mathbb{Z}_q$, the decryption oracle does not provide any useful information to the adversary. However, I am not sure whether the ability to obtain blinded decryptions of messages outside the valid message space helps the adversary or not.

Could someone please provide pointers towards either an attack or a proof of security? Thanks.



Your Answer

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