Hi,

I think that I'm missing something in the definition of non-malleability— we require that for every message $m$ the adversary will succeed with negligible probability.

A silly example— fix any PKE that is CCA secure and define $f_n(x)$ to be 1 if $x=0^n$ and 0 otherwise. Then by defining $\cA$ on input $(pk, ct)$ to return the encryption of 1 under the public key, don't we actually succeed on every message which is not $0^n$ with very high probability? In fact it seems that for every function and any message we can construct an adversary which succeeds on the message.

What am I missing?

Thanks,

Eliran