Score:1

What does it mean for public keys to be in coNP

in flag

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?

Score:3
ng flag
  • 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

  1. 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)$.

  2. for DLOG type assumptions, given some $(g, g^s)$, we can similarly efficiently verify that $g^s$ takes this form via the witness $s$

  3. 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.

poncho avatar
my flag
"For essentially all known public-key encryption schemes, public keys form an NP set"; the only way for a public-key encryption scheme to avoid this is to have an impractical public/private key generation step - that is, one that takes a superpolynomial amount of time. Otherwise, it is obvious how to use that key generation step as an efficient verifier (with the seed being the nondeterministic input)
Mark avatar
ng flag
@poncho there are "practical" ways you could have public keys of scheme fail to form an NP set, for example if key generation requires interaction. While for encryption this is silly, it technically could be done, and there are other primitives (various multiparty ones) where it is less silly.
poncho avatar
my flag
I would disagree with the multiparty example; the all the multiparty computations (and all interactions) can be emulated in polytime (which it will if each party computes in polytime, and there are only a polynomial number of parties), then that emulation could be used as a verifier.
Mark avatar
ng flag
@poncho if emulation of the form you claim exists, it implies that any 2 player interactive protocol (say with some constant number of rounds for simplicity) is in NP, e.g. PH collapses to $coNP = NP$, which is not thought to hold. There are some nuances with using randomness (an example that doesn't appeal to interaction of public keys not being an NP set would be a situation where verification is randomized, where they would be an MA set I think), but even those aren't enough to save your argument --- most complexity theorists simultaneously think P = BPP and PH doesn't collapse iirc.
bagheera avatar
in flag
Hey Mark, thanks!!. I read Brassards original paper where he showed if f is a OWF where domain NP, and Range Co-NP then under the assumption of P != NP, if you wanted to prove that f^-1 is NP-hard will result in NP=coNP. I think that proof was actually quite simple, but I'm not completely following the restatement in this paper. Are the following statments true: set of messages (NP set) Set of public keys (CoNP sets) [for examples RSA, DL, LWE] I guess for the proof to carry over I would need (Enc_pk(m), pk) to also be in coNP, but how do i verify if Enc_pk(m) is a bad encryption?
Mark avatar
ng flag
@bagheera I wouldneed to read Brassard to answer, and cannot find a copy. It seems that Goldreich+Goldwasser state you should carefully read theorem 2, item 2ii though. I would be surprised if the final restatement involved the "set of messages" at all though, as there is usually no hard problem assumed to be related to these. It seems plausible they are viewing $m\mapsto (Enc_pk(m), pk)$ as a OWF of sorts, and appealing to Brassard for the problem of inverting it. That being said, I can't say anything concrete without a copy of Brassard.
bagheera avatar
in flag
No problem, found a copy on ieee through school. Thanks for your answers they've been extremely helpful
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.