Re: [CFRG] hash_to_field requires implementing a new 25519 field op

"Riad S. Wahby" <rsw@jfet.org> Wed, 21 July 2021 22:41 UTC

Return-Path: <rswatjfet.org@gmail.com>
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 BD9913A2D3D for <cfrg@ietfa.amsl.com>; Wed, 21 Jul 2021 15:41:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.649
X-Spam-Level:
X-Spam-Status: No, score=-1.649 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.249, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no 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 ROBrEwRS9oZ6 for <cfrg@ietfa.amsl.com>; Wed, 21 Jul 2021 15:41:16 -0700 (PDT)
Received: from mail-qk1-f171.google.com (mail-qk1-f171.google.com [209.85.222.171]) (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 992EB3A2D38 for <cfrg@irtf.org>; Wed, 21 Jul 2021 15:41:16 -0700 (PDT)
Received: by mail-qk1-f171.google.com with SMTP id m68so3674085qke.7 for <cfrg@irtf.org>; Wed, 21 Jul 2021 15:41:16 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=yikmW2MeXFq2gsfd+hi3OEL/WBTXdCAe4K9a6vfhtHA=; b=tshm/1sKy72KHaxhNRlxmj8gqZOawaiXoQXq8ALFtii6hJVPKxSPFteNJfVP7LdZjg dKJw6PsG5Qgm9dbv7/c/c8w+g75PrNvh+YurX7GJiwzqNBgzS5Ayi34KZL4SaQNDRpd8 ziWbxopTf4pCev+8SeT3Q1atZwrZ+7fx85dA4vRcFNyRsFRSongd2FrxmphBY34UJwIm Km7R0MpH4oNwwElo5x53lSy3cGLzAzfHS37t5bPScgASG7TbG7Fua1Ofkq92KHYQNss7 2FFqx0ZS9kvgKHl92GzRdIbz6cEcU7Un7ofqc5FtvVRrfnWrXWhkvAAHcfExgPNWyRnM Xahw==
X-Gm-Message-State: AOAM5315ZNmCzivxeYyBNMKM8VG16tWzJrCMDo3e4xRbY93X6zXN0N8o jnasVHeNlbk7m+Krs2OSouQ=
X-Google-Smtp-Source: ABdhPJxnz41D75Z3FYy+SdycX5CAo0SBraSmv7aHlYcNsgw2WdJHEsohUey4mdaCRP4/z8qA8ueikQ==
X-Received: by 2002:a37:92c6:: with SMTP id u189mr36174119qkd.237.1626907275387; Wed, 21 Jul 2021 15:41:15 -0700 (PDT)
Received: from localhost (mobile-166-170-21-67.mycingular.net. [166.170.21.67]) by smtp.gmail.com with ESMTPSA id e2sm12200186qkn.69.2021.07.21.15.41.14 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Wed, 21 Jul 2021 15:41:14 -0700 (PDT)
Date: Wed, 21 Jul 2021 18:41:13 -0400
From: "Riad S. Wahby" <rsw@jfet.org>
To: Loup Vaillant-David <loup@loup-vaillant.fr>
Cc: Filippo Valsorda <filippo@ml.filippo.io>, cfrg@irtf.org
Message-ID: <20210721224113.qvbezr3pqbdy5bck@kaon.local>
References: <aaa46d82-f05d-4558-8a2a-6d945fe9cb1d@www.fastmail.com> <20210721191123.i3f33p3qvkwxlbtl@kaon.local> <c16f6fe23f1b11e9a311f4b57cabfbef4a517b58.camel@loup-vaillant.fr>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <c16f6fe23f1b11e9a311f4b57cabfbef4a517b58.camel@loup-vaillant.fr>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/kG9wPUGUpyo8piOm8fNHmxQz8Sw>
Subject: Re: [CFRG] hash_to_field requires implementing a new 25519 field op
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: Wed, 21 Jul 2021 22:41:23 -0000

Hello Loup,

Loup Vaillant-David <loup@loup-vaillant.fr> wrote:
> Wait a minute, that reduction is not *nearly* as large as you make it
> out to be.  Let's take a look at Curve25519's ref10 implementation on
> SUPERCOP. You would think that because the result of the multiplication
> (before carry propagation) is stored in 10 64-bit signed integers, the
> number they represent easily exceeds 2^512, or even approaches 2^640.

Our messages crossed, but in general the product of two residues mod p
will be as large as p^2 - 2p + 1, which is roughly log2(p^2) bits as I
claimed. The code you link does some of that reduction implicitly, but
the same trick can be used on a 384-bit number. See my message from ~5
minutes ago to Filippo.

Or, as Rene points out in parallel, if we do not demand absolutely the
fastest reduction we can implement it using field operations directly,
which is what I did in the pairing-plus crate, for example:
    https://github.com/algorand/pairing-plus/blob/master/src/bls12_381/fq.rs#L471

Cheers,

-=rsw