[messaging] [curves] Generating nonces for Schnorr signatures

[David Leon Gil]

> The curve is designed to be ~2^223 secure.  If the scalar and nonce are
chosen by a pseudorandom generator and function, respectively, with ~2^256
security, then they are indistinguishable from random for an attacker
acting within the security estimate.

Agreed. (And I, personally, find this approach unobjectionable.)

The argument for generating a random key is this:

Suppose, contrary to your assumption, that the hash is not a good PRF on
its restriction from in:bytes[0..] - > out:bytes[0..] to in:bytes[32] ->
bytes[48]. The subspace of private keys may be biased in a predictable way;
in theory you could use a distinguisher to reduce the amount of work in a
rho algorithm. (By only considering points that are within that subspace.)

(E.g. there is some evidence that the first word of SHA-1's output is
further from uniform distributed than the last word.)

But there is another argument for generating keys your way; it eliminates
any ephemeral channel to leak private keys via public keys.* (So I'd
actually prefer, in the stored-key approach, to slightly reduce the size of
the 'protokey' to the security strength of the curve.)

- David

*Though I am unsure whether there is a cheap way to do this with EC keys
analogous to the RSA case. (Is there a proof that it's hard that I don't
know?)
On Jun 25, 2014 10:21 PM, "Mike Hamburg" <mike at shiftleft.org> wrote:

>
> On 6/25/2014 9:57 PM, Watson Ladd wrote:
>
> On Wed, Jun 25, 2014 at 4:37 PM, Trevor Perrin <trevp at trevp.net> wrote:
> > So Ed25519 and Goldilocks are similar in generating the private scalar
> > and signing nonce from a "master key":
> >
> > Ed25519
> > --------
> > private_scalar[32], nonce_key[32] = SHA512(master_key[32])
> > sig_nonce[32] = SHA512(nonce_key[32] || message) % q
> >
> > Goldilocks
> > --------
> > private_scalar[56] = SHA512("derivepk" || masterkey[32])
> > sig_nonce[56] = SHA512("signonce" || masterkey[32] || message ||
> > masterkey[32]) % q
> >
> >
> > Qs
> > * Is it weird that the range for Goldilocks private scalar and nonce
> > is size 2^256, rather than the size of the main subgroup (~2^446)?
>
> I can't think of a way to break it. Bernstein mentions something similar
> for curve25519,  with s, md5 (s) as the secret key.
>
> The curve is designed to be ~2^223 secure.  If the scalar and nonce are
> chosen by a pseudorandom generator and function, respectively, with ~2^256
> security, then they are indistinguishable from random for an attacker
> acting within the security estimate.
>
> -- Mike
>
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140630/eaf0d882/attachment.html>