[Cfrg] EdDSA private key restrictions & composability (Re: normative references)

[Adam Back <[e-mail]>]

On Wed, Jan 15, 2014 at 10:02:01AM -0800, Paul Lambert wrote:
> - unclear guidelines on important security topics
>    E.g.
>      ed25519 has restrictions on the secret key structure for ECDH
>      Does this extend to other curves?

Actually on this narrow topic re Ed25519 curve for EdDSA uses, I noticed
this also.  I think bit 254 being 1 could be optional so (Curve25519 has the
same private key restrictions for ECDH) so long as constant time montgomery
addition starts from bit 254 regardless.  And the remaining hard code is the
lowest 3 bits 000 but that which I presume is precomputed multiplication by
the cofactor, as seen in the verification relation 8sG=8R+8H(R,Q,m)Q. 
(Using ECDSA labelling G is base, Q=dG pub key).

The paper seems quite unclear and hard to pick apart and maybe the algorithm
just a little too much speed hacked.  The above seems to break
composability.  Ie derived public keys (Q_i = Q+M(c,i)G) where c is a
shared-secret, i is a counter; bitcoin uses this for backup and offline
security reasons.  Similar examples abound: threshold signatures, blind
signatures; one of the exciting thing to me about seeing EdDSA adopted is
that it is a Schnorr variant, and Schnorr has much simpler multiparty,
threshold and even blinding.  ECDSA has no blinding and DSA blinding is a
monstrosity involving Damgard-Jurik's generalized variant of Paillier as a
substep!  But some of these things are lost or complicated by the unusual
private key restrictions, which I think if I'm not mistaken are just related
to tiny optimizations or otherise redundant defenses against variable time
execution which can be otherwise restated.

These kind of questions might or might not be in scope for the draft,
depending on your point of view.  (But anyway if anyone feels like
expounding on the above, on list or offlist, I would quite practically
interested :)

Adam