What is the implication of $VNP = VP$ to cryptography schemes such as Elliptic curve/Abelian Variety/Arithmetic Geometry based cryptography? Are there any papers or books that talk about sophisticated encryption techniques and the possible complexity classes they belong to?

There seems to be a negative implication for RSA if $VNP = VP$. On the other hand no OWF should exist if $VNP = VP$. However relatively nothing is known about frailty of candidate OWF from Arithmetic Geometry if $VNP = VP$. Will these be safe?

  • $\begingroup$ Why do you say that no OWF should exist if VP=VNP? I agree that if P=NP then no OWF should exist, but VP=VNP is quite a bit weaker than that, a priori... $\endgroup$ Sep 18, 2015 at 15:03
  • 1
    $\begingroup$ @JoshuaGrochow $VNP=VP\implies P/poly=NP/poly\implies NP\subseteq P/Poly\implies$ no $\mathsf{PRG}$s exist $\implies$ no $\mathsf{OWF}$s exist (from problem $7.3$, theorem $7.11$ here people.seas.harvard.edu/~salil/pseudorandomness/prgs.pdf) $\endgroup$
    – user34945
    Dec 30, 2015 at 4:34
  • $\begingroup$ @Arul: Indeed. Sorry, I was thinking by default of complexity-theoretic (rather than cryptographic) OWFs, which have only a uniform hardness (not nonuniform). In fact, your reasoning seems to answer the question: any candidate OWF cannot be a cryptographic OWF (that is, against nonuniform adversaries) if VP=VNP. Over finite fields this is literally true, and over fields of characteristic zero it is true under GRH. $\endgroup$ Dec 31, 2015 at 0:15
  • $\begingroup$ @JoshuaGrochow sorry I dont follow 'is there diff b/w crypto OWF and complexity theoretic OWF?' For GRH as required are you using burgeisser's work? I thought OWF are defined against P/poly adversaries as in included links or more strongly against BPP adversaries. What is a complexity theoretic OWF? $\endgroup$
    – user34945
    Dec 31, 2015 at 0:25
  • 2
    $\begingroup$ @Arul: They are sometimes also called "worst-case OWF" (since crypto OWF are also typically defined by an average-case notion of hardness); they exist iff P neq UP. See the references on the zoo entry for UP, as well as papers that cite those papers. $\endgroup$ Dec 31, 2015 at 2:01


Your Answer

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