Why does the EdDSA use a 2b-bit hash function?

Question

The EdDSA signature of a message $M$ under key $k$ is created as:

1. Define $r=H(h_b,....,h_{2b−1},M)\in\{0,1,...,2^{2b}−1\}$.

2. Define $R=rB$.

3. Define $S=(r+H(\underline R,\underline A,M)s)\bmod\ell$.

Output $(\underline R,\underline S)$ as signature (where $\underline S$ is the $b$-bit little-endian encoding of $S$).

My question is: why does it use of $2b$-bit hash function? What will happen if we use of $b$-bit hash function in the above equations? The $r$ in 1 has $2b$-bit, but it computes the $R=rB$ in 2 and $S$ in 3 at the $\ell$ module. Note that $\ell$ has $b$-bit. Why don't we use the hash function with $b$-bit output? Is there any security problem with this?

Answer 1

Why does EdDSA use of $2b$-bit hash function?

It insures $r\bmod\ell$ is almost uniformly distributed in $\{0,1,\ldots\ell-1\}$. That's explained at the end of the section on Pseudorandom generation of $r$, which also explains $H$ of $b+61$-bit would be enough for this purpose.

Is there any security problem with this?

Update: I know no I'm told there's is actually a purely cryptographic attack if we reduce $H$ to $b$-bit. It

leaks the private key to lattice or FFT algorithms on relatively small numbers of signatures, with Howgrave–Graham/Smart or Bleichenbacher. The setting is very weak: you just need to get a decently large number of signatures on distinct messages, not even chosen messages, and—bam—the private key falls out. In the Minerva attack, there was a separate side channel giving additional information about the per-signature secrets even if they were uniformly distributed; this enabled the adversary to do rejection sampling to give a nonuniform distribution for the lattice attack. With b-bit secrets reduced modulo the curve order, the distribution is already nonuniform enough for the lattice attack.

Turns out that a less-than-uniform modulo $\ell$ not only invalidate the security argument, it allows an attack! It also (and more badly) affects ECDSA, and there was precedents as explained earlier in the section on Pseudorandom generation of $r$ of Bernstein's paper.