Paillier equality test under the same key

Question

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?

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.