Subject: [Cfrg] draft-irtf-cfrg-hash-to-curve

From: Armando Faz <[email-masked]>
Date: Tue, 21 May 2019 15:35:15 -0700

Dear,

Inside the hash2curve draft, there is defined a Hash2Field function, which
maps bit strings uniformly on elements of Fp.

Let k be the security parameter, and let Fp be a prime field such that
log2(p) = 2k.

We want to construct a function F : {0,1}* -> Fp using an auxiliary
cryptographic hash function h: {0,1}* -> {0,1}^b. Hence, F can be
constructed as
     F(x) := h(x) mod p.
However, for this function to be indistinguishably from a random oracle,
the size of h must be at least b >= 3k to get a statistical distance Pr =
1/2^k .

Example.
For 256-bit primes, SHA384 or SHA512 satisfy the requirements. ( k=128,
log2(p) = 256, b >= 384 )

Issue:
For a 448-bit or 512-bit prime, there is no such a large hash with b>672
and b>768, resp.

Possible approaches:
  a) Use h(x) := SHAKE256(x, b), this function allows to specify the size
of the output as required.
  b) Use a concatenation of hash outputs. For example, concatenating the
output of SHA256:
           h(x) := SHA256(x || 0) || SHA256(x || 1) || ...
      until get the desired b bits.

The question is: which option is best suited for obtaining F on large
primes?

-- 
Armando Faz
Cloudflare Inc.