IETF Logo Mail Archive

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

Michele Orrù <lists@tumbolandia.net> Fri, 12 April 2019 15:40 UTC

Return-Path: <lists@tumbolandia.net>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 5C390120372 for <cfrg@ietfa.amsl.com>; Fri, 12 Apr 2019 08:40:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level:
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H2=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 8L_Gbs2BVVwD for <cfrg@ietfa.amsl.com>; Fri, 12 Apr 2019 08:40:19 -0700 (PDT)
Received: from relay3-d.mail.gandi.net (relay3-d.mail.gandi.net [217.70.183.195]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 883351202F0 for <cfrg@irtf.org>; Fri, 12 Apr 2019 08:40:18 -0700 (PDT)
X-Originating-IP: 207.242.54.131
Received: from [10.10.1.159] (unknown [207.242.54.131]) (Authenticated sender: lists@tumbolandia.net) by relay3-d.mail.gandi.net (Postfix) with ESMTPSA id 7151660008; Fri, 12 Apr 2019 15:40:15 +0000 (UTC)
From: Michele Orrù <lists@tumbolandia.net>
To: Armando Faz <armfazh@cloudflare.com>, cfrg@irtf.org
Cc: Anita DURR <anita.durr@psl.eu>, Brice Minaud <brice.minaud@ens.fr>
References: <1853a156-df76-7999-df2b-1ea120a85b40@tumbolandia.net> <20190406174721.GA108882@LK-Perkele-VII> <4f83a1a8-70bc-e9b4-838a-ee5209cbf329@tumbolandia.net>
Message-ID: <6ac3ad81-cdb6-27e4-fa16-26a242c63808@tumbolandia.net>
Date: Fri, 12 Apr 2019 08:40:13 -0700
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1
MIME-Version: 1.0
In-Reply-To: <4f83a1a8-70bc-e9b4-838a-ee5209cbf329@tumbolandia.net>
Content-Type: multipart/mixed; boundary="------------EBEB754B6BCD7D67FA66E802"
Content-Language: en-US
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/uLzkw3AdGUIp397tmU7slxFWvgM>
Subject: Re: [Cfrg] Recommended bit length before truncating a hash mod p
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: Fri, 12 Apr 2019 15:40:20 -0000

On 4/8/19 4:19 PM, Michele Orrù wrote:
> - (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.

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

v2.23.0 | Report a Bug | By Email