Re: [Cfrg] Recommended bit length before truncating a hash mod p

[Michele Orrù <[e-mail]>]

Hi people,


I'm sorry if this reply comes out as a different thread - just subscribed.

Together with Anita (in Cc.) we independently thought that the draft 
could be a bit more precise about how many bits to take before reducing 
mod p. More specifically, the sentence:

```
To address this, our hash2base algorithm greedily takes as many bits as
possible before reducing mod p, in order to smooth out this bias. This is
preferable to an iterated procedure, such as rejection sampling, since 
this can be hard to reliably implement in constant time.
```

is imprecise: a developer should know exactly how many bits to add (for 
the current security level) in order to have a distribution 
indistinguishable from uniformly random mod p. Taking into account what 
has been said so far, we would like to change the above sentence to:

```
In order to smooth out this bias, our hash2base algorithm takes 64 + 
floor(log2(p)) + 1 bits in order to smooth out this bias. This is 
preferable to an iterated procedure, such as rejection sampling, since 
this can be hard to reliably implement in constant time.
```

This should at least give an intuition that adding 64 bits makes the 
difference of the two distributions statistically negligible.
What do you think? Is this relevant?

In case one wants to have a deeper look, I sketched a git patch here:
https://github.com/mmaker/draft-irtf-cfrg-hash-to-curve/commit/af0fd8f27f016a8cad1e61819a075eeacd2ebeae

Cheers,
-- 
μ.