On Jul 21, 2009, at 3:11 PM, Hal Finney wrote:
The first is equivalent to: knowing g^(xy) is it impossible to deduce g^x, where y = H(g^x). Define Y = g^x, then y = H(Y) and g^(xy) = Y^H(Y). The
question is then:

Given Y^H(Y) can we deduce Y?
To make a simple observation: H matters. If H(z)=0 for all z, then we discard all information and clearly no inversion is possible. If H(z)=1 for all z, then inversion is trivial. If H(z)=n for any fixed non-negative integer n, the problem is exactly discrete log - given (g^x)^n, find (g^x).

Now, these are obviously uninteresting hashes. Let's take the simplest 1-1 onto hash, H(z)=z. Then we are asking if, given (g^x)^x, we can find g^x. This feels like the same kind of problem as discrete log, but the additional structure is disturbing. Other simple forms also seem like they might leak information. For example, H(z)=g^z asks the question of whether, given z^z, we can find z.

If H(z) is "random" - i.e., if you use some real cryptographic hash - it's hard to see how you would get a proof, except maybe something of the form "for almost all H drawn from some population, the problem is hard". But of course one always makes such arguments before one has a proof....

                                                        -- Jerry

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Reply via email to