Zooko's semi-private keys

[Jerry Leichter]

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 at metzdowd.com