I was reading this paper.
And on Page 2 the following claim was made: Consider a public-key encryption scheme with a deterministic encryption algorithm, and suppose that the set of valid public-keys is in coNP. Then if retrieving the plaintext from the (ciphertext, public-key) pair is NP-Hard then NP = coNP.
I guess what I don't completely understand is what it means for a set of public-keys to be in co-NP? Is there maybe an intuitive example?
NP is the set of decision problems that are efficiently verifiable. Given an instance $x$ of the decision problem, there is a short "proof" $w$ that, given the pair $(x, w)$, one can efficiently verify that $x$ is true.
coNP is the set of decision problems that are efficiently refutable. Given an instance $x$ of the decision problem, there is a short "dis-proof" $w$ that, given the pair $(x, w)$, one can efficiently verify that $x$ is false.
For essentially all known public-key encryption schemes, public keys form an NP set. What does this mean? Given some public key $pk$, there is some additional information $sk$ (the secret key) such that one can efficiently verify that $pk$ is a public key with respect to the secret key $sk$. For example
for RSA, $N = pq$. Given some $N'$ which may or may not take this form, we can efficiently verify it does via the witness $(p, q)$.
for DLOG type assumptions, given some $(g, g^s)$, we can similarly efficiently verify that $g^s$ takes this form via the witness $s$
for lattice/code-based schemes, given some $(A, As + e)$, we can efficiently verify that $(As + e)$ takes this form via the witness $(s, e)$.
This is all to say that, given the secret key of some PKE, it is typically quite easy to verify the public key is structured correctly (and not simply some random element).
Now, a public key would be in a coNP set if, given some "$pk$" that is not a public key (and instead is simply some "random element"), one can efficiently verify this. For example, for RSA, if someone gives you some $N$ that cannot be written as $N = pq$, you can efficiently verify this via a complete factorization of $N = \prod_i p_i^{e_i}$. $((p_1, e_1),\dots,(p_k,e_k))$ therefore serves as a witness to $N$ not being an RSA public key, and in this sense RSA public keys are both an NP set and a coNP set.
The claim of that section of the paper is that the precondition
encryption is deterministic and the set of public-keys form a coNP set.
is restrictive. I personally view the first part of this as being more restrictive than the second. For example, it seems likely to me that in all three examples I mentioned above, public keys form a coNP set. In the first two examples it is obvious, and in the third I think strong enough basis reduction could/should work as a witness, in particular if $B$ is a short enough basis for the dual of $\mathcal{L}(A)$, then $(BAs + Be)$ will be an unusually short vector for a "true LWE" sample, but will be uniformly random for a random sample, e.g. will be a coNP witness.
