tarcieri/semiprivate.md

## semiprivate.md

      
    Raw
  

              semiprivate.md
            
          
    Semiprivate Keys

🚨 DANGER: INSECURE! 🚨

This may have seemed like a great idea in 2013, but the repeated "set/clear bits", a.k.a. clamping phases at each level of the hierarchy slowly subtract key strength.
Don't use this as described. Check out Ristretto.
Original text

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)
	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)