[144620] in cryptography@c2.net mail archive
Re: Zooko's semi-private keys
daemon@ATHENA.MIT.EDU (Jerry Leichter)
Wed Jul 22 11:57:40 2009
Cc: cryptography@metzdowd.com,
jamesd@echeque.com,
tanja@hyperelliptic.org,
zooko@zooko.com
From: Jerry Leichter <leichter@lrw.com>
To: Hal Finney <hal@finney.org>
In-Reply-To: <20090721191112.2111814F6E1@finney.org>
Date: Wed, 22 Jul 2009 08:13:05 -0400
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 majordomo@metzdowd.com
