4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ A classic machine solving a co-NP problem can trivially flip the result and solve the complementary NP problem. $\endgroup$
    – Fractalice
    Mar 31 at 6:58
  • $\begingroup$ 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. $\endgroup$
    – user4242
    Mar 31 at 7:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – ckamath
    Mar 31 at 11:09
  • $\begingroup$ 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. $\endgroup$
    – user4242
    Mar 31 at 12:39
  • 1
    $\begingroup$ @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. $\endgroup$
    – user4242
    Apr 2 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.