# VNP = VP versus complexity classes in Arithmetic Geometry

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?

• 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... Sep 18 '15 at 15:03
• @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)
– user34945
Dec 30 '15 at 4:34
• @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. Dec 31 '15 at 0:15
• @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?
– user34945
Dec 31 '15 at 0:25
• @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. Dec 31 '15 at 2:01