I have a similar question to this one: Is an equality test possible when using paillier crypto?

However I want to do the following:

  1. Given the Paillier Cryptosystem.
  2. Given the function $f(input)$, which both Alice and Bob have.
  3. $f()$ is a deterministic function.
  4. Both Alice and Bob have the input of this function.

Alice encrypts a message $m=f(input)$ with Alice's public key and publishes $enc(m)$.

Is it know possible for Bob to verify, knowing $m=f(input)$, if $dec(enc(m))=m$, but without knowing Alice's private key?

  • 1
    $\begingroup$ As I argued in the other question: Anybody who can verify a guess for an encryption can trivially break the IND-CPA security of the scheme. $\endgroup$
    – SEJPM
    May 20, 2017 at 10:56
  • $\begingroup$ Is the knowledge of $f$ limited to Alice and Bob? $\endgroup$
    – SEJPM
    May 21, 2017 at 17:58

1 Answer 1


If you intend to make $f$ public, or that $f$ does not depend on the secret key, that's not going to work:

  • The Paillier cryptosystem is proven to be IND-CPA under the decisional composite residuosity assumption.
  • If a function $f$ exists, like you describe in the question, this function would immediately break IND-CPA
  • By contraposition, function $f$ does not exist (under the assumption that the cryptosystem is IND-CPA).

However, if $f$ is actually the decryption function with the private key hard coded or any modification of this, it would work. However, that means Bob might be able to extract the private key from $f$. If you want that to be computationally hard, you will need to prove this property.

That last part is quite difficult and maybe even impossible. I am not aware of a property like that for the Paillier cryptosystem. Composite moduli do have some properties which might be suitable. For example computing an $e$-th root of a fixed public element is computationally hard but knowing this root does not reveal the factorization of the modulus. But I don't know how you could adapt this in the Paillier cryptosystem.


Your Answer

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

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