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)