Determine secure amount of private key modulo bias

[paulmillr]

For a curve like secp256k1, which has 32-byte (256-bit) $G$, we take 32+8 bytes (256+64 bits) from CSPRNG and mod-divide it by curve order $n$. This follows FIPS guidelines and has $2^{-64}$ bias:

https://github.com/paulmillr/noble-curves/blob/8c48abe16acddaaabfaf75b9d669f515f129a67d/src/abstract/weierstrass.ts#L847-L855

1. FIPS 186 B.4.1 was replaced by FIPS 186-5 in Appendix A.2.1 this year. The amount of bytes was changed a bit
2. It was suggested by an outside auditor that this could be adjusted to match the security level of a curve, as per draft-irtf-cfrg-hash-to-curve:

To control bias, hash_to_field instead uses random integers whose length is at least ceil(log2(p)) + k bits, where k is the target security level for the suite in bits. Reducing such integers mod p gives bias at most 2^-k for any p; this bias is appropriate when targeting k-bit security. For each such integer, hash_to_field uses expand_message to obtain L uniform bytes, where

L = ceil((ceil(log2(p)) + k) / 8)

These uniform bytes are then interpreted as an integer via OS2IP. For example, for a 255-bit prime p, and k = 128-bit security, L = ceil((255 + 128) / 8) = 48 bytes.

I think it's fine to adjust the amount of bytes. Several questions still arise:

1. What does a $2^{-64}$ bias actually mean? Is there any realistic attack? How many keys would an attacker need to walk through before gaining meaningful advantage?
2. How was the formula from hash-to-curve draft calculated? Why does it consider 384 bits from csprng "match 128-bit security" for 256-bit $G$?
3. What other standards are out there with regards to bias?
4. DJB used $2^{-259}$ bias for eddsa nonce: r = mod(sha512(prefix, msg), ed25519.l). Why not $2^{-128}$?
5. How should a generic rule look like? We can't use Fp.BYTES + Math.ceil(Fp.BYTES/2), because it's field - not curve group.
   • For ed25519, which has $P = 2^{255}-19$ and $n=2^{252}+27742317777372353535851937790883648493$ that would mean we'll fetch 253+127=380 bits - which is rounded to 384 (48 bytes)