On Jul 21, 2009, at 3:11 PM, Hal Finney wrote:

The first is equivalent to: knowing g^(xy) is it impossible todeduce g^x,where y = H(g^x). Define Y = g^x, then y = H(Y) and g^(xy) = Y^H(Y).Thequestion 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