[tahoe-dev] Fwd: Zooko's semi-private keys

[Zooko Wilcox-O'Hearn]

Folks:

Hal Finney is a very good thinker about cryptography.  Years ago, the  
Freenet developers used to call him by the nickname "Gandalf" because  
he would wander into their mailing list and bequeath sage wisdom.   
I've sometimes wished he would do the same for Tahoe-LAFS, so I'm  
delighted to see that he posted the following to the cryptography  
mailing list.

Regards,

Zooko

Begin forwarded message:

> From: hal at finney.org ("Hal Finney")
> Date: Tuesday, July,2009-07-21 13:11:12 0 MDT
> To: cryptography at metzdowd.com, jamesd at echeque.com,  
> tanja at hyperelliptic.org, zooko at zooko.com
> Subject: Zooko's semi-private keys
>
> Zooko's proposal for "semi-private keys" is worthy of discussion  
> here I think.  The full idea is in http://allmydata.org/~zooko/ 
> lafs.pdf but I will present it here for your enjoyment (I should  
> emphasize that I played no part in any of the development of this  
> idea, I just read his PDF). Apologies in advance for any  
> misunderstandings or misrepresentations I make. I also want to  
> apologize for using the term "secret key" rather than Zooko's  
> preferred "private key" so that we can call it SK and then the  
> public key is PK.  The semi-private key will be SPK. Below, "^"  
> refers to repeated iteration of the group operation, in a given group.
>
> With most public key systems, knowing the SK allows you to deduce  
> the PK, but of course you can't go the other direction:
>
> SK -> PK
> PK /-> SK
>
> Zooko wishes to introduce an intermediate data structure, the semi- 
> private key or SPK, which fits in between:
>
> SK -> SPK
> SPK -> PK
> PK /-> SPK
> SPK /-> SK
>
> From the SK you can deduce the SPK, and from the SPK the PK, but  
> you can't go backwards.
>
> The reason for this is he wants to issue signatures with the SK  
> which can be verified by people holding the SPK and by (different)  
> people holding the PK; and further he wants to be able to create an  
> encryption key from the SPK, which will (therefore) also be known  
> to the holder of the SK, but not to holders of the PK. In this way  
> the holder of an SK can have two groups of verifiers: PK holders  
> can check signatures but not read data, while SPK holders can both  
> check signatures and read data.
>
> The part that makes this interesting is that it is desired that all  
> of SK, SPK and PK are as small as possible for a given security  
> level. This is because of the goal in the Tahoe object-capability  
> distributed file system of using these keys as identifiers for  
> files. There would be 3 different identifiers for a file in this  
> system, corresponding to the SK, SPK and PK associated with that  
> file, and each identifier would give the different levels of  
> cryptographic access described above.
>
> If we didn't have this requirement, we could solve it trivially by  
> augmenting the SK with an ordinary encryption key k, and defining  
> SPK as (PK,k). Then the information arrows above would be met. But  
> we have increased the SK and SPK key sizes by the size of k, which  
> may be a very substantial percentage when we are dealing with EC keys.
>
> Zooko proposes a specific alternative in his paper, a modification  
> of DSA (equivalently, ECDSA). In ordinary DSA, SK is a secret  
> exponent x in some group, and PK is g^x for some generator g of the  
> group. Zooko defines:
>
> y = H(g^x) using hash function H
>
> and proposes that:
>
> SK is xy
> SPK is g^x
> PK is g^(xy)
>
> It is easy to see that this satisfies the information arrows SK ->  
> SPK -> PK. There are no obvious ways to go the other way, but  
> analysis is needed to verify that. As far as key size, neither SK  
> nor PK gets any bigger, and SPK is the same size as PK.
>
> DSA signatures are then done in the usual way, using xy in place of  
> the usual secret exponent x. For reference, and slightly  
> simplified, the usual DSA formulas are:
>
> r = g^k for some random k;
> s is derived from sk * rx = h (mod the group order)
>
> where h is the message hash. Then Zooko's modification merely  
> replaces x by xy (keep in mind that sometimes y is defined as the  
> public key g^x in DSA descriptions, but here y is different, y = H 
> (g^x)):
>
> r = g^k for some random k;
> s is derived from sk * rxy = h (mod the group order)
>
> Zooko asks for cryptographic community review of this proposal. I  
> believe I can sketch a couple of simple proofs in the random oracle  
> model that being able to forge signatures, knowing either SK or  
> SPK, would allow forging ordinary DSA. This message is getting  
> pretty long though, so perhaps others will wish to chime in.
>
> The remaining questions are whether PK /=> SPK holds, and SPK /=>  
> SK. The second part is easily shown to reduce to discrete log.  
> Suppose we have an oracle which, given g^x, produces x*H(g^x). Then  
> we can just divide by H(g^x) and get x, turning it into a discrete  
> log oracle.
>
> 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?
>
> Ideally we'd like to show that an oracle that could solve this  
> could be used to find arbitrary discrete logs or break some other  
> standard assumption, but I can't see how to do it. (I also can't  
> see how to go the other way, from a discrete log oracle to  
> something that can solve this - seems like a hard problem.)
>
> Hal Finney