Ed25519-based semi-private keys

semiprivate.md

Semiprivate Keys

Semi-private keys are an expansion of the traditional idea of asymmetric keys, which have a public/private keypair, to N keys which can each represent a different capability level. In the degenerate case, a semi-private key system has 3 different types of keys. These are, to use the Tahoe terminology:

• writecap: can publish new ciphertexts
• readcap: can read/authenticate ciphertexts
• verifycap: can authenticate ciphertexts

One of the goals of Tahoe is to keep the capability tokens for each of these short. Tahoe goes to pretty extreme lengths to do this, like symmetrically encrypting an RSA key and storing it along with a file.

I definitely applaud what they've done there and also believe that short capabilities are more useful. The real goal of a semi-private key system is to produce short capability tokens which are more convenient for users to distribute (potentially in non-digital forms)

The problem is Tahoe's description of semi-private keys is intended for DSA, however I would like to implement semi-private keys for use with NaCl. NaCl uses elliptic curve cryptography, so the implementation is slightly different.

This is, as best I understand it, how to implement it in terms of NaCl:

Constants:

• P = NaCl base point (standard group element)
• l = Order(P)

Functions:

• H(): SHA512 truncated to 256-bits + set/clear bits

Variables:

• k = random Ed25519 seed
• x = H(k)
• Q = x*P (semiprivate key)
• y = H(Q) mod l
• z = x*y mod l (computed Ed25519 private scalar)
• R = y*Q (Ed25519 public key)

Test:

assert(R == z*P)

Figure 1: Semiprivate Key Generation

Figure 2: Ed25519 (unmodified)

Credits

Semiprivate keys were originally Zooko's idea. The basic idea is described in section 6.1 of the Tahoe-LAFS paper.

SAGE code courtesy Samuel Neves

semiprivate.sage

import hashlib
 
p = 2^255 - 19;
E = EllipticCurve(GF(p), [0,486662,0,1,0]);
P = E.lift_x(9);
l = P.order();
 
x = ZZ.random_element(l);
Q = x*P;
y = int(hashlib.sha512(str(Q)).hexdigest(), 16) % l;
z = x*y % l;
R = y*Q;
assert(R == z*P)