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
