2021.06.16 15:08:23 (1405150260435980300) from Daniel J. Bernstein, replying to "Steven Galbraith (@EllipticKiwi)" (1404898197093249024):
Reading more I see 6.2 saying that to your knowledge "all implementations" reduce; but [20] points to libgcrypt as a counterexample. The reduction takes an extra line of code, so skipping it is the simplest thing to do---and, hey, look, another line of defense against Minerva.
2021.06.16 15:15:42 (1405152103979372546) from Daniel J. Bernstein:
On a different note, I'm puzzled by the choice to use asymptotic formalisms that by definition don't apply to a concrete signature system such as Ed25519. Quantifying the reduction cost (1) is necessary and (2) allows the definitions and theorems to be simplified (skip lambda).
2021.06.14 11:50:48 (1404375760874270723) from "Steven Galbraith (@EllipticKiwi)":
I could have been more precise in my comments. Fixing a leading bit is ok. But want distribution to be close to uniform. Since p \approx 2^{255} and #E \approx p this is easy. But your choice in EdDSA to use bit 2^{254} and 3 MSB=0, means only 2^{251} possible.
2021.06.14 11:55:51 (1404377032725651464) from "Steven Galbraith (@EllipticKiwi)", replying to "Steven Galbraith (@EllipticKiwi)" (1404375760874270723):
If you'd set bit 255 instead, or not zeroed the last 3 bits, then all would be good. It's interesting that you took a much more conservative approach to the hashing/de-randomization (I would not have gone as far as 512 bit hashing).
2021.06.15 22:01:30 (1404891836645208066) from Daniel J. Bernstein, replying to "Steven Galbraith (@EllipticKiwi)" (1404377032725651464):
Yes, the suggestion in Section 5.3 of https://cr.yp.to/papers.html#multischnorr ends up setting bit 255 instead. The hashing is under very different constraints: doubling the output size simplifies parts of the design, helps protect implementations (as we saw with Minerva), and doesn't cost much.
2021.06.15 22:26:46 (1404898197093249024) from "Steven Galbraith (@EllipticKiwi)":
Sorry I missed this when writing my evaluation report.