<p>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?</p>

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

CC BY-SA 3.0
2015-09-18T15:03:09.397Z
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...
Joshua Grochow
CC BY-SA 3.0
2015-12-31T00:15:13.860Z
@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.
Joshua Grochow
CC BY-SA 3.0
2015-12-31T01:06:39.870Z
@Arul: Yes, I was referring to Burgisser for GRH. Crypto OWF is defined against P/poly (or *more weakly* against BPP), and usually, as far as I understand it, need not be 1-1. Complexity OWF is typically defined as a 1-1 function computable in poly-time whose inverse is not computable in poly time (so, it's 1-1 by definition, and is defined against a P adversary).
Joshua Grochow
CC BY-SA 3.0
2015-12-31T02:01:52.883Z
@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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#up), as well as papers that cite those papers.
Joshua Grochow
CC BY-SA 3.0
2015-12-31T05:23:35.017Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/33668/discussion-between-joshua-grochow-and-arul).
Joshua Grochow
<cc.complexity-theory><cr.crypto-security><conditional-results><one-way-function>
VNP = VP versus complexity classes in Arithmetic Geometry
v s
# VNP = VP versus complexity classes in Arithmetic Geometry

(Asked by: username_0 on 2011-07-11)

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?

**Tags:** cc.complexity-theory, cr.crypto-security, conditional-results, one-way-function
> **Comments:**
> **username_1**: 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...  
> **username_1**: @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.  
> **username_1**: @Arul: Yes, I was referring to Burgisser for GRH. Crypto OWF is defined against P/poly (or *more weakly* against BPP), and usually, as far as I understand it, need not be 1-1. Complexity OWF is typically defined as a 1-1 function computable in poly-time whose inverse is not computable in poly time (so, it's 1-1 by definition, and is defined against a P adversary).  
> **username_1**: @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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#up), as well as papers that cite those papers.  
> **username_1**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/33668/discussion-between-joshua-grochow-and-arul).  

---

## 0 answers

