# Cryptomania and NP $\cap$ co-NP

Cryptomania is usually presented as the Impagliazzo's world, which gives us public-key cryptography under the assumption that trapdoor OWFs exist. For purposes of constructing public-key cryptography we also want the underlying problem to be in $$NP \cap coNP$$ as described in here. Are there any papers, which explore this particular requirement in relation to Impagliazzo's worlds?

Edit 02/04/2021: After some more digging I managed to find the answer, which describes the $$NP \cap coNP$$ requirement, as such I am restructuring this question, to only ask about results on impagliazzo's 5 worlds in relation to this property.

• A classic machine solving a co-NP problem can trivially flip the result and solve the complementary NP problem. Mar 31 at 6:58
• i am aware of that, what i am curious about is whether the cryptomania results of constructing cryptosystems from trapdoor OWFs, also capture the intuition that the problems should be at the intersection of NP and co-NP and whether that intuition is correct. Mar 31 at 7:01
• I think this goes back to Brassard (this paper, behind a paywall unfortunately). It is conjectured that public-key cryptography corresponds to $\mathbf{SZK}\cap\mathbf{NP}$. You can read more about that here. Mar 31 at 11:09
• I believe Brassard's paper is close enough to what I was looking for. If you want to turn it into an answer that would be nice. I might do that in a couple days if noone does, I have to process the details in the generalization section first though. Mar 31 at 12:39
• @fgrieu cryptomania is a name for possible resolution to P v NP Russell Impagliazzo coined along with 4 more and it's relatively standard in research papers on cryptography, it identifies a specific world with trapdoor owfs. changing it to cryptography does not make much sense. Apr 2 at 12:27