Zooko's semi-private keys

[Hal Finney]

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