Re: [Cfrg] Interest in an "Ed25519-HD" standard?

[Taylor R Campbell <[e-mail]>]

> Date: Tue, 21 Mar 2017 12:42:10 -0700
> From: Tony Arcieri <[e-mail]>
> 
> Hierarchical key derivation (also sometimes described as "semiprivate keys"
> or "key blinding") is an increasingly popular technique for generating
> unlinkable child keys from master public and private keys.
>
> [...]
> 
> I'd be curious to know if anyone else would be interested in collaborating
> on a draft for such a standard, which can be a synthesis of the existing
> work in this space.

This sounds like a good idea, because (a) it's mostly straightforward
to invent a scheme in terms of, e.g., EdDSA, that basically works, but
(b) there are some little details that need to be nailed down.


Here's a quick summary for signatures.  First, for reference, standard
signatures have three operations -- keygen, sign, and verify:

   priv, pub <- keygen(seed)
   sig       <- sign(priv, msg)
   ok        <- verify(pub, sig, msg)

Security contract: If seed is uniform random, then:

   Attacker knowing pub with oracle for msg |---> sign(priv, msg)
   can't find sig for which verify(pub, sig, msg) passes if msg not
   given to oracle.

(Maybe attacker can find novel signatures for messages already signed
-- malleability is a story for another day.  Quantifying cost left as
an exercise for the reader.)

Blinded-key signatures, or perhaps `1-level hierarchical signatures',
have five operations, with a natural extension to multi-level schemes:

   priv, pub <- keygen(seed)
   tpriv     <- blindpriv(priv, tweak)
   tpub      <- blindpub(pub, tweak)
   sig       <- sign(tpriv, msg)
   ok        <- verify(tpub, sig, msg)

Security contract: If seed is uniform random, then:

(a) Attacker knowing pub with oracle for (tweak, msg) |--->
    sign(blindpriv(priv, tweak), msg) can't find sig for which
    verify(blindpub(pub, tweak), sig, msg) passes for any (tweak, msg)
    not given to oracle.  (Again, malleability is another story.)

(b) Attacker with oracle for tweak |---> blindpub(pub, tweak) can't
    distinguish tpub from any other tpub' derived from independent
    uniform random seed' for any tweak not given to oracle.


Example of standard signatures: EdDSA on twisted Edwards curve E(F_q)
over (b - 1)-bit prime field F_q with base point B of n-bit order l,
cofactor 2^c (c < n <= b), and 2b-bit hash H, ignoring details of
encoding *except* for the clamp function:

- pub is point A on curve E(F_q);
- sig is (R, s) for point R and integer 0 <= s < l;
- verification equation is 2^c s B = 2^c R + 2^c H(R,A,msg) A;

- priv = seed is opaque b-bit k,
  a = clamp(low b bits of H(k)),
  A = a B,
  r == H(high b bits of H(k), msg) (mod l),
  R = r B,
  s == r + H(R,A,msg) a (mod l);
  thus, s B = r B + H(R,A,msg) a B
            = R + H(R,A,msg) A, as required.

`clamp' maps an integer to the form 2^n + k*2^c for k < 2^(n - c) by
clearing bits above n, setting bit n, and clearing the low c bits.

This is done only so that the private-key-to-public-key map of EdDSA
is equivalent to the corresponding map in, e.g. X25519, which demands
of secret scalars
(a) a fixed position for the high bit, to efficiently evaluate the
Montgomery ladder in constant time, and
(b) a multiple of the cofactor, to avoid revealing residues of the
secret scalar to an attacker who supplies points on a small subgroup.

I emphasize clamp because although it is irrelevant to the security of
EdDSA as far as I know, it is prescribed by standards and performed by
implementations, so we must address it if we want to enable reuse of
existing standard EdDSA code.


Example of a naive blinded-key variant of EdDSA, say B1-EdDSA, which I
am *not* claiming guarantees the security contract but which serves as
an illustration for discussion -- Dmitry's paper goes into much more
detail about existing schemes and their engineering considerations,
and I encourage reading it for anyone who wants more than my quick
summary here:

- pub is point A on curve E(F_q),
- tpub is point A' = t A, where t = clamp(low b bits of H(A, tweak))
- sig is (R, s) for point R and integer 0 <= s < l,
- verification equation is 2^c s B = 2^c R + 2^c H(R,A,A',msg) A',

- priv = seed is opaque b-bit k,
  a = clamp(low b bits of H(k)),
  A = a B,
  tpriv is b-bit scalar a' == t a (mod l) together with A' = t A = t a B,
  r == H(high b bits of H(k), A', msg) (mod l),
  R = r B,
  s == r + H(R,A,A',msg) a' (mod l);
  thus, s B = r B + H(R,A,A',msg) a' B
            = r B + H(R,A,A',msg) t a B
            = R + H(R,A,A',msg) t A
            = R + H(R,A,A',msg) A', as required.

Some convenient properties of this particular construction:

- B1-EdDSA-verify(tpub, sig, msg) = EdDSA-verify(A', sig, A'||msg).

- B1-EdDSA-sign(tpriv, msg) is almost EdDSA-sign with secret scalar a'
  of message A'||msg, except the EdDSA secret key is the seed k, not
  the scalar derived from it -- but EdDSA implementations almost
  certainly have an internal subroutine to compute this nevertheless.

- B1-EdDSA-blindpriv(priv, tweak) == t a (mod l) is multiplication of
  public and secret scalars modulo l, which EdDSA implementations are
  practically guaranteed to already have, perhaps with an additional
  addend (which can just be set to zero).

Some caveats:

- B1-EdDSA-blindpub(pub, tweak) = t A requires multiplication of a
  *possibly secret* curve point A by a public scalar.  I'm not sure
  that EdDSA implementations will necessarily have constant-time
  scalar multiplication of secret curve points, though they probably
  do.

- Some variants I have seen multiply by 2^c (mod l) instead of
  clearing the low c bits.  Other variants clamp (or multiply by 2^c
  (mod l)) only one of the scalars -- a, t, or a' -- so that in
  multi-level hierarchical schemes, different-length paths produced by
  different factorizations of scalars have the same multiplicity of
  the cofactor.  These practical considerations do not -- as far as I
  know -- affect signature security, but they do affect compatibility.

- The security contract did not mention secrecy of the tweak.  Is that
  important for applications?  Not for any I know of, but my knowledge
  is limited.