Appendix A: Signature scheme with key blinding

Key derivation overview

As described in [IMD:DIST] and [SUBCRED] above, we require a "key blinding" system that works (roughly) as follows:

There is a master keypair (sk, pk).

        Given the keypair and a nonce n, there is a derivation function
        that gives a new blinded keypair (sk_n, pk_n).  This keypair can
        be used for signing.

        Given only the public key and the nonce, there is a function
        that gives pk_n.

        Without knowing pk, it is not possible to derive pk_n; without
        knowing sk, it is not possible to derive sk_n.

        It's possible to check that a signature was made with sk_n while
        knowing only pk_n.

        Someone who sees a large number of blinded public keys and
        signatures made using those public keys can't tell which
        signatures and which blinded keys were derived from the same
        master keypair.

        You can't forge signatures.

        [TODO: Insert a more rigorous definition and better references.]

Tor's key derivation scheme

We propose the following scheme for key blinding, based on Ed25519.

(This is an ECC group, so remember that scalar multiplication is the trapdoor function, and it's defined in terms of iterated point addition. See the Ed25519 paper [Reference ED25519-REFS] for a fairly clear writeup.)

Let B be the ed25519 basepoint as found in section 5 of [ED25519-B-REF]:

      B = (15112221349535400772501151409588531511454012693041857206046113283949847762202,
           46316835694926478169428394003475163141307993866256225615783033603165251855960)

Assume B has prime order l, so lB=0. Let a master keypair be written as (a,A), where a is the private key and A is the public key (A=aB).

To derive the key for a nonce N and an optional secret s, compute the blinding factor like this:

           h = H(BLIND_STRING | A | s | B | N)
           BLIND_STRING = "Derive temporary signing key" | INT_1(0)
           N = "key-blind" | INT_8(period-number) | INT_8(period_length)
           B = "(1511[...]2202, 4631[...]5960)"

  then clamp the blinding factor 'h' according to the ed25519 spec:

           h[0] &= 248;
           h[31] &= 63;
           h[31] |= 64;

  and do the key derivation as follows:

      private key for the period:

           a' = h a mod l
           RH' = SHA-512(RH_BLIND_STRING | RH)[:32]
           RH_BLIND_STRING = "Derive temporary signing key hash input"

      public key for the period:

           A' = h A = (ha)B

Generating a signature of M: given a deterministic random-looking r (see EdDSA paper), take R=rB, S=r+hash(R,A',M)ah mod l. Send signature (R,S) and public key A'.

Verifying the signature: Check whether SB = R+hash(R,A',M)A'.

  (If the signature is valid,
       SB = (r + hash(R,A',M)ah)B
          = rB + (hash(R,A',M)ah)B
          = R + hash(R,A',M)A' )

  This boils down to regular Ed25519 with key pair (a', A').

See [KEYBLIND-REFS] for an extensive discussion on this scheme and possible alternatives. Also, see [KEYBLIND-PROOF] for a security proof of this scheme.