[curves] ECC with semiprivate keys

[Brian Warner]

On 2/13/14 2:18 PM, Tony Arcieri wrote:

> I've been curious about semiprivate keys for awhile. The concept is a
> bit hard to describe, so I'll refer to section 6.1 of the Tahoe paper

Yeah, Zooko and I wanted those for Tahoe-LAFS, to capture the stack
(lattice?) of filecaps, going from most powerful (writecap), down to
readcap, down to verifycap. What we really wanted was a generalized
N-deep stack of them (where the version in that paper had N=3),
described roughly here:

 https://tahoe-lafs.org/pipermail/tahoe-dev/2008-October/000828.html

(because we were also interested in the "writecap / readcap /
deep-verifycap / verifycap" stack, where N=4)

If K1 is the most-powerful key, and Kn is the least-powerful, then you
should be able to sign things with any of the keys, and derive Kn from
any of them, and use Kn to verify signatures made by any key (and you
should be able to tell which key was used to make the signature).

We also started to sketch out what useful public-key encryption
semantics we could get out of this (maybe with the order reversed: K1
can decrypt messages created by any of the other keys, but K2 is less
powerful, etc). But we didn't get very far with it. It'd also be neat if
you could get keys that could be used for both signing and encryption,
but I don't think it's possible.

The core issue was that you need two distinct one-way functions, and
there must be an associative-ish pair of ways to combine them. What we
wrote down for N=3 was:

 x = random
 define y = g^x
 K1 = x
 signkey = x*y = x*H(g^x) = K1*H(g^K1)
 K2 = g^x = g^K1
 K3 = g^(x*y) = g^(x*H(g^x)) = (g^x)^H(g^x) = K2^H(K2)
 verifykey = K3 = g^signkey

So you can get from K1->K2->K3=verifykey, and from K1->signkey. And you
also get the necessary DSA relationship between signkey and verifykey. I
think you can generalize this to N>=4, but I don't remember offhand what
it would look like.

I tried once to translate this multiplicative-notation prime-field stuff
into an additive-notation Ed25519 version, but got confused and didn't
finish. I think that's what tarcieri has accomplished.

One concern I couldn't shake was that the clamp() function in Ed25519
was doing something important that was beyond my understanding, so I was
worried that I'd fail to meet some subtle requirement and thus wind up
being vulnerable to something that normal Ed25519 keys were protected
against, like pubkeys that aren't really group elements, or something.

cheers,
 -Brian