Re: [Cfrg] Fwd: New Version Notification for draft-barnes-cfrg-mult-for-7748-00.txt

Watson Ladd <> Tue, 05 November 2019 03:08 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 6EF09120073 for <>; Mon, 4 Nov 2019 19:08:13 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Status: No, score=-1.997 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id h9Yxzmby8dG2 for <>; Mon, 4 Nov 2019 19:08:10 -0800 (PST)
Received: from ( [IPv6:2a00:1450:4864:20::134]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id DD98312006F for <>; Mon, 4 Nov 2019 19:08:09 -0800 (PST)
Received: by with SMTP id v8so13834801lfa.12 for <>; Mon, 04 Nov 2019 19:08:09 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=gWRCMKpqO1tHxGqn050QhQ+iMsrMO2rG1JG/rxL/akg=; b=rAvaJb2fnJ9G2KMcN5iLKawo/0NyPKPqL2D/HbjVvFPtOZ3Jxw04d8FCT3lOYECa6f 5eDW8MhuezxSPSKyvITHXZFV8y2Yj9adLpqeP6+4NSZeCBXGaZaebDsfFqKQCee3Yn5Y hVeOA/yqC54ldnMtp+4pZvESIoRREE1mFZ1eBMM7jnnemXcYoKe83uI9fsQCYUSltnl+ CyQK65aEkkoFntJObY0i3djpKQZuyEDAH8ViVG1T95AY48IatstwZvHWYDqfJ79ntFWy PrMOim4tU6gj/CcA/suOTDpOFYB+L22zYKy2tLt8QxsyNG3eHICwrKo0XIm+pcPZ3oVQ fQKQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=gWRCMKpqO1tHxGqn050QhQ+iMsrMO2rG1JG/rxL/akg=; b=K6roHWJcQpyd54x+eZKBWb3AFeQHjy7hKoDpPF+sbrPFHJwrG7Ikvx5ixaK20jtbuM hTKDKKcuoJovkmGim4sKRQ9YIdUtv5al715tFCgWbWYD594xwuU0h0OVkIg8rxnHqfYs NtxXmF2MtomJ0DR3jOfA4uR/DHtrRjX61myw2aEKZ/cW2xhkGWbToFSwiIDoyXoICAff HZeLni3S19RaloeqJojmwoJvS3AE+vQRM+qsA3l6qjigOC7Ekvzx/xZlr7nX/V3vvJ74 KGMccPgmHEi/5xLXxOsXENDrqvCL1FYfp/0EP5feN3TYP44oWBsBmhVWu/9R2c6vojq7 zb/A==
X-Gm-Message-State: APjAAAWptSpY1iKwP0LSuPAeuxOpOVSs4pXoOHhJn72iL08meJF0SBkg BnxmPACv5cihCRY7Ki6YTpyUXF0EwbO2PrtMUgc=
X-Google-Smtp-Source: APXvYqyDt+7Z6YqG/HHKfnQVibDK7xMiAuo7ODx2vqOON7mH/5LsB1cBlec93TQv4seFbdB7xu3wq41TKjKSq9ON7ow=
X-Received: by 2002:a19:40cf:: with SMTP id n198mr18944839lfa.189.1572923287869; Mon, 04 Nov 2019 19:08:07 -0800 (PST)
MIME-Version: 1.0
References: <> <>
In-Reply-To: <>
From: Watson Ladd <>
Date: Mon, 4 Nov 2019 22:07:56 -0500
Message-ID: <>
To: Richard Barnes <>
Cc:, Sandro Coretti <>, Joel Alwen <>
Content-Type: multipart/alternative; boundary="000000000000d520a7059690bd90"
Archived-At: <>
Subject: Re: [Cfrg] Fwd: New Version Notification for draft-barnes-cfrg-mult-for-7748-00.txt
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 05 Nov 2019 03:08:13 -0000

On Mon, Nov 4, 2019 at 6:53 PM Richard Barnes <> wrote:

> Hi CFRG folks,
> This draft is a proposal to address a deficiency in X25519 and X448 that
> has been noted a couple of times on this list (e.g., [1]), namely the fact
> that multiplication of scalars and point multiplication do not commute.
> While looking into applications of updateable public-key encryption in the
> context of MLS [2], my co-authors came upon a solution that while not
> perfect, works in all but a statistically insignificant number of cases.

If you have a ladder that doesn't require the high bit to be in any
particular place, then you're fine.  What's the application where you
cannot modify the implementation to compute n*X for any n, not just one of
a particular length? Secondly the calculation assumes d uniformly random:
but if d is say 2, then whether or not the generation fails is entirely
dependent on the second bit of y if we write sk=2^254+8y, as 2*sk is
2^255+8*2*y, which if it's in the fail range proves y<x/2, which is true
for about half the possibly y if I understand the notation correctly. What
I don't know is if you can do this again, and extract another bit, and
another, etc.

> The draft describes how to do scalar multiplication in a way that is
> compatible with point multiplication in the X25519 and X448 groups,
> describes the cases where these algorithms can fail, and provides methods
> for detecting failure.  While "move to Ristretto" is also a solution to
> this problem, it seemed like a solution for X25519 / X448, even if partial,
> might have a slightly faster path to deployment.
> As with any -00 draft, feedback is very welcome!  If Go is your preferred
> medium, we've also implemented the relevant concepts in the corresponding
> GitHub repo [3].
> Thanks,
> --Richard
> [1]
> [2]
> [3]
> ---------- Forwarded message ---------
> From: <>
> Date: Mon, Nov 4, 2019 at 6:44 PM
> Subject: New Version Notification for
> draft-barnes-cfrg-mult-for-7748-00.txt
> To: Richard L. Barnes <>sx>, Joël Alwen <>om>, Sandro
> Corretti <>
> A new version of I-D, draft-barnes-cfrg-mult-for-7748-00.txt
> has been successfully submitted by Richard L. Barnes and posted to the
> IETF repository.
> Name:           draft-barnes-cfrg-mult-for-7748
> Revision:       00
> Title:          Homomorphic Multiplication for X25519 and X448
> Document date:  2019-11-04
> Group:          Individual Submission
> Pages:          10
> URL:
> Status:
> Htmlized:
> Htmlized:
> Abstract:
>    In some contexts it is useful for holders of the private and public
>    parts of an elliptic curve key pair to be able to independently apply
>    an updates to those values, such that the resulting updated public
>    key corresponds to the updated private key.  Such updates are
>    straightforward for older elliptic curves, but for X25519 and X448,
>    the "clamping" prescribed for scalars requires some additional
>    processing.  This document defines a multiplication procedure that
>    can be used to update X25519 and X448 key pairs.  This algorithm can
>    fail to produce a result, but only with negligible probability..
>    Failures can be detected by the holder of the private key.
> Please note that it may take a couple of minutes from the time of
> submission
> until the htmlized version and diff are available at
> The IETF Secretariat
> _______________________________________________
> Cfrg mailing list

"Man is born free, but everywhere he is in chains".