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

From: Michele Orrù <[email-masked]>
Date: Tue, 2 Apr 2019 10:07:13 +0200

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,
-- 
μ.

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 6 Apr 2019 20:47:21 +0300

On Tue, Apr 02, 2019 at 10:07:13AM +0200, Michele Orrù wrote:
> 
> 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:
> 
> ```
> 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:
> 
> ```
> 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.
> ```
> 

In fact, the uniformity can heavily depend on p. Any p very close to
power of two gives very uniform results. And one needs lots of extra
bits to increase the uniformity further.

Looking at Curve25519, Curve448 and NIST P-384, the SD is <2^-200 and
that won't bulge with 64 extra bits.

NIST P-256 has much bigger base SD (~2^-32), and that starts to move
with ~30 extra bits. 64 extra bits seems to decrease SD by factor of
~2^64.

-Ilari

---

From: Michele Orrù <[email-masked]>
Date: Mon, 8 Apr 2019 16:19:33 +0200

> with ~30 extra bits. 64 extra bits seems to decrease SD by factor of

Hi Ilari,

that's right, good point. It seems to us that there are two 
possibilities now:

- (as you note) we list the curves for which 64 extra bits are needed in 
order to smooth out the bias, i.e. the curves for which p = 2^λ - r is 
very close to a power of two, or more precisely (1-r/p) r/2^(λ-1)  < 2^-64.

- or we just advise developers to always take 64 + log(p) + 1 bits.
Unless those extra bits do not come cheap, it is perhaps the easiest 
solution?

In both cases, we think that the standard could be more explicit about 
how much entropy is needed for a (close to) uniform distribution. Thoughts?

PS. adding Brice in Cc; I forgot him in my previous mail.
--
μ.

---

From: Michele Orrù <[email-masked]>
Date: Fri, 12 Apr 2019 08:40:13 -0700

> very close to a power of two, or more precisely (1-r/p) r/2^(λ-1)  < 2^-64.

sorry, here I meant *not* needed.

I chatted with Armando yesterday, and he kindly asked I put (for the 
record) the formal proof of what Anita, Brice and me claim. So, ehm, 
here you go: https://share.riseup.net/#SUp7Ypm3uXVagn0lSoPLNA (source 
attached)

I'm sorry I can't point you to a specific paper, asking around this 
seems to be folklore in the crypto community as it's a simple counting 
argument.

Hoping this will be useful,
--
μ.

---

From: Michele Orrù <[email-masked]>
Date: Fri, 12 Apr 2019 08:32:45 -0700

here you go.