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.

Improve this question
$\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, 2021 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, 2021 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, 2021 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, 2021 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, 2021 at 12:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.