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 --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
