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

Hi Christopher,
for this exact problem, we follow the approach described by Mehmet:

Hash512(x) = Hash256(0||x) || Hash256(1||x)

This way we can take up to 512 bits using a 256-bit hash function. You can
find an example implementation of this (for Keccak256) here:
https://github.com/nucypher/pyUmbral/blob/master/umbral/random_oracles.py#L84

Regards,
David

> ---------- Forwarded message ----------
> From: Mehmet Adalier <madalier@antarateknik.com>
> To: Christopher Wood <christopherwood07@gmail.com>, <cfrg@irtf.org>
> Cc:
> Bcc:
> Date: Thu, 21 Mar 2019 19:11:47 -0700
> Subject: Re: [Cfrg] Recommended bit length before truncating a hash mod p
> Would this work?
>
> 1) generate two hashes with two different x values,
> 2) concatenate the two outputs
> 3) take however many high order bits you need (with at least 64 additional
> bits per spec)
>
> In our regular P256 implementation we use a 512-bit value before we
> perform reduction.
>
> mA
>
> On 3/21/19, 6:20 PM, "Cfrg on behalf of Christopher Wood" <
> cfrg-bounces@irtf.org on behalf of christopherwood07@gmail.com> wrote:
>
>     Hi folks,
>
>     In draft-irtf-cfrg-hash-to-curve, we define a utility function called
>     `hash2base` as follows [1]:
>
>     ~~~
>     hash2base(x).  This method is parametrized by p and H, where p is the
>     prime order of the base field Fp, and H is a cryptographic hash
>     function which outputs at least floor(log2(p)) + 1 bits.  The function
>     first hashes x, converts the result to an integer, and reduces modulo
>     p to give an element of Fp.  We provide a more detailed algorithm in
>     Appendix C.7.
>     ~~~
>
>     Some existing standards [2] recommend taking at least log2(p) + 64
>     bits “so that bias produced by the mod function … is negligible.” If
>     we were to follow this guidance for hash2curve, we’d lose out on
>     several ciphersuite combinations, such as P-256 and Curve25519 with
>     SHA256.
>
>     So, our question to the group is, how many extra bits are necessary?
>
>     Thanks,
>     Chris
>
>     [1]
> https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-03#section-4
>     [2]
> https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar3.pdf
>
>     _______________________________________________
>     Cfrg mailing list
>     Cfrg@irtf.org
>     https://www.irtf.org/mailman/listinfo/cfrg
>
>