[math-fun] Reverse is harder?
Much or all of cryptography depends on the claim that there is a bijective map F such that computing y=F(x), is a lot easier than computing x=Finverse(y). For example, if F maps (a,b,c) to (b^a mod c, b, c) where gcd(b,c)=1, then many people think/hope that Finverse is a lot harder than F ("discrete logarithm problem"). But my QUESTION is: what is the best result one can actually PROVE of the form "Finverse is a lot harder than F"? ============================================== Dhananjay S. Phatak pointed out to me (then I improved by consulting Joerg Arndt's book...) that the "Gray coding" problem is a provable (pitifully weak, but provable) example. In C-language notation g = x ^ (x>>1) will convert bitstring x to Gray code g. This is implementable by a parallel circuit with depth=1, and #gates=wordlength-1. Reverse operation accomplished by: x = g; x ^= x>>1; x ^= x>>2; x ^= x>>4; x ^= x>>8; x ^= x>>16; ... keep going until word length. This can be done by a circuit with O(N) gates, but the depth is now log2(wordlength) not 1, and this is best possible in the sense that no circuit made of (<=2-input, <=2-output) binary logic gates can do it with less depth. --- More generally, multiplying y=Mx where M is an NxN sparse matrix, and x,y each are N-vectors (in some field) is easy to do forward (assume at most a constant number of nonzeros per row of M): order N field operations and time; parallelizes to depth=O(1) if at most. But computing x=Minverse y is provably harder, requiring depth of order log(N) at least. The proof is to observe that in general each entry of x will depend on all N entries of y. [I actually do not know how to do it in less than order N^2 operations, but I do not have a proof that's best possible.] Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
="Warren Smith" <warren.wds@gmail.com> Much or all of cryptography depends on the claim that there is a bijective map F such that computing y=F(x), is a lot easier than computing x=Finverse(y).
But my QUESTION is: what is the best result one can actually PROVE of the form "Finverse is a lot harder than F"?
Dhananjay S. Phatak pointed out to me (then I improved by consulting Joerg Arndt's book...) that the "Gray coding" problem is a provable (pitifully weak, but provable) example.
Funny you should mention this--coincidentally today I was recalling that long ago Whit Diffie mentioned something about proving the existence of trap door functions being one of the open problems in public key cryptography. Whit, are you lurking, and inclined to replace my vague amnesia with facts?
On Wed, Feb 13, 2013 at 8:47 PM, Warren Smith <warren.wds@gmail.com> wrote:
Much or all of cryptography depends on the claim that there is a bijective map F such that computing y=F(x), is a lot easier than computing x=Finverse(y).
For example, if F maps (a,b,c) to (b^a mod c, b, c) where gcd(b,c)=1, then many people think/hope that Finverse is a lot harder than F ("discrete logarithm problem").
But my QUESTION is: what is the best result one can actually PROVE of the form "Finverse is a lot harder than F"?
The problem is that what you'd really like is an example where F can be computed in polyomial time, but Finverse cannot. But if F is in P, then Finverse is in NP, so proving that any F has this property is at least as hard as proving that P != NP. Andy
Last year I attended a workshop at Princeton entitle "Impagliazzo's Worlds" (named after Russell Impagliazzo who started this line of inquiry) about life would be like (complexity wise) re: the P = NP? problem. It turns out to be much more varied than I would have thought. I've stolen what's below from Lance Fortnow's blog. Note, especially "Pessiland". Victor In that paper he describes five possible worlds and their implications to computer science. Algorithmica: P = NP or something "morally equivalent" like fast probabilistic algorithms for NP. This was the world I described last week but looking back at Impagliazzo's paper, he does a nicer job. Heuristica: NP problems are hard in the worst case but easy on average. Pessiland: NP problems hard on average but no one-way functions exist. We can easily create hard NP problems, but not hard NP problems where we know the solution. This is the worst of all possible worlds, since not only can we not solve hard problems on average but we apparantly do not get any cryptographic advantage from the hardness of these problems. Minicrypt: One-way functions exist but we do not have public-key cryptography. Cryptomania: Public-key cryptography is possible, i.e. two parties can exchange secret messages over open channels. Impagliazzo does not guess which world we live in. Most computer scientists would say Cryptomania or Minicrypt. On Wed, Feb 13, 2013 at 11:37 PM, Andy Latto <andy.latto@pobox.com> wrote:
On Wed, Feb 13, 2013 at 8:47 PM, Warren Smith <warren.wds@gmail.com> wrote:
Much or all of cryptography depends on the claim that there is a bijective map F such that computing y=F(x), is a lot easier than computing x=Finverse(y).
For example, if F maps (a,b,c) to (b^a mod c, b, c) where gcd(b,c)=1, then many people think/hope that Finverse is a lot harder than F ("discrete logarithm problem").
But my QUESTION is: what is the best result one can actually PROVE of the form "Finverse is a lot harder than F"?
The problem is that what you'd really like is an example where F can be computed in polyomial time, but Finverse cannot. But if F is in P, then Finverse is in NP, so proving that any F has this property is at least as hard as proving that P != NP.
Andy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Ignoring depth, and just counting gates, I've heard rumors that the best known result for reversing an xor circuit is a ratio of 1.5+epsilon. I.e., there is a K-input, 1-1, N-gate-dag-circuit (no feedback) of xor gates whose inverse circuit (also a dag of xor gates) requires 1.5N+change gates. The example is pretty simple: the inputs are arranged in a polygon, each is xored with a neighbor or two and maybe with the total parity. For reversing a sparse NxN matrix multiply, it appears you need to compute a few inverse values directly at cost few*N. But then you may be able to capitalize on the sparseness to compute the remaining values cheaply from the forward-direction equations, solving one equation at a time. The big unknown here is how large "few" must be. I encountered this problem when I was trying to solve the finite-field equation X^2 + X = A over GF[2^155]. My field polynomial is U^155+U^62+1. The low bits of X and A are forced to 0, to make the problem 1-1. My best answers (lowest gate count), for several different 2^odd field sizes, use a direct method to compute 20-40 values, and then fill in the others at a cost of a couple of gates each. Rich --------- Quoting Warren Smith <warren.wds@gmail.com>:
Much or all of cryptography depends on the claim that there is a bijective map F such that computing y=F(x), is a lot easier than computing x=Finverse(y).
For example, if F maps (a,b,c) to (b^a mod c, b, c) where gcd(b,c)=1, then many people think/hope that Finverse is a lot harder than F ("discrete logarithm problem").
But my QUESTION is: what is the best result one can actually PROVE of the form "Finverse is a lot harder than F"?
==============================================
Dhananjay S. Phatak pointed out to me (then I improved by consulting Joerg Arndt's book...) that the "Gray coding" problem is a provable (pitifully weak, but provable) example. In C-language notation
g = x ^ (x>>1) will convert bitstring x to Gray code g. This is implementable by a parallel circuit with depth=1, and #gates=wordlength-1.
Reverse operation accomplished by: x = g; x ^= x>>1; x ^= x>>2; x ^= x>>4; x ^= x>>8; x ^= x>>16; ... keep going until word length.
This can be done by a circuit with O(N) gates, but the depth is now log2(wordlength) not 1, and this is best possible in the sense that no circuit made of (<=2-input, <=2-output) binary logic gates can do it with less depth.
---
More generally, multiplying y=Mx where M is an NxN sparse matrix, and x,y each are N-vectors (in some field) is easy to do forward (assume at most a constant number of nonzeros per row of M): order N field operations and time; parallelizes to depth=O(1) if at most. But computing x=Minverse y is provably harder, requiring depth of order log(N) at least. The proof is to observe that in general each entry of x will depend on all N entries of y.
[I actually do not know how to do it in less than order N^2 operations, but I do not have a proof that's best possible.]
Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Andy Latto -
Marc LeBrun -
rcs＠xmission.com -
Victor Miller -
Warren Smith