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

Armando Faz <armfazh@cloudflare.com> Tue, 21 May 2019 22:35 UTC

Return-Path: <armfazh@cloudflare.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 55BAE120073 for <cfrg@ietfa.amsl.com>; Tue, 21 May 2019 15:35:28 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.01
X-Spam-Status: No, score=-2.01 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, T_DKIMWL_WL_HIGH=-0.01] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cloudflare.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id cVpGO0JwZhXe for <cfrg@ietfa.amsl.com>; Tue, 21 May 2019 15:35:27 -0700 (PDT)
Received: from mail-it1-x130.google.com (mail-it1-x130.google.com [IPv6:2607:f8b0:4864:20::130]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2552412004C for <cfrg@irtf.org>; Tue, 21 May 2019 15:35:27 -0700 (PDT)
Received: by mail-it1-x130.google.com with SMTP id m3so399951itl.1 for <cfrg@irtf.org>; Tue, 21 May 2019 15:35:27 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=mime-version:from:date:message-id:subject:to; bh=Y2GWpusBBVe+olJMqoWA9jIKsFru5m7tp5KMUaxUfM0=; b=vmIsP74qR/xn093yMRZPNs9111wruCP5a2PZf8TBtj7Fvnxn5t/E9j6t8lM/KGXZJv a5/vkhi5X/RmBoO3DbLFQwWSGjbf0QEagmtyLaTVnynGdLjKLNVxJ7k9cjefVMskwS0m PBOJV7/HCwG5aj67vV9RiJkToKVhObtu8Wd2U=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=Y2GWpusBBVe+olJMqoWA9jIKsFru5m7tp5KMUaxUfM0=; b=ITo4mSwDOhow90UWInAeoBUJ+uej3KmIOryicDOnqPZO4dMM0QSE1U7vrZyri5JPMB jYXcLd6yhPcrupAIuQ+PndOLBIMMI5J+H3VmTMc+JY8WOsHdK7HQDLaAUQjb8KegNLsG D9LYT3oAnBWoTrJPDN/vxn+CahMZgNaPVo21kagrC1/0FBlA6iOgBoyIzLheGv0FrWsb pX6b6XOXtznobjkaFmoj1JMsedZDtWvfeUjjszTBjT0Tl7QjdlPiJToR8lYqKZp9ZKKn by8xFN58AzSiMuW8X6NJoopCYY7Fky7YM/ASdrMpzF3RR6PeGGAh2p5DbPxZVe8iTQ++ kyvQ==
X-Gm-Message-State: APjAAAUaRbx2VYkwbmEerGq3VRxzc/k4NLLHviuliG0UOO61Mgs20xfN YWgv8aVXORLWPbxFm+vpAqfDk7cS/Y0YTy//P9KQsUih0tPSMA==
X-Google-Smtp-Source: APXvYqxgBIFfz35YiCB2Y+XssCucRcer9wPc8yJbwkFZ5jYCP63eOSDL/dLY3+vqvuzrofVi+1nCIueKpEJc7iPXCR4=
X-Received: by 2002:a24:c242:: with SMTP id i63mr5736644itg.89.1558478125941; Tue, 21 May 2019 15:35:25 -0700 (PDT)
MIME-Version: 1.0
From: Armando Faz <armfazh@cloudflare.com>
Date: Tue, 21 May 2019 15:35:15 -0700
Message-ID: <CABZxKYkLGJbMu8BW-bYjedkYahot3fp-u8C8N4OmHR3Ch8dFAg@mail.gmail.com>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="0000000000001674c905896d77dc"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/YfT6GukVQSqt0Gbn1VVbMcO2niM>
Subject: [Cfrg] draft-irtf-cfrg-hash-to-curve
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 21 May 2019 22:35:28 -0000


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 .

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

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

Armando Faz
Cloudflare Inc.