Re: [Cfrg] Curve25519 lacks private/public homomorphism?

Richard Barnes <> Mon, 04 February 2019 23:28 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 284D412870E for <>; Mon, 4 Feb 2019 15:28:33 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.052
X-Spam-Status: No, score=-0.052 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.142, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=1.989, RCVD_IN_DNSWL_NONE=-0.0001] 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 Ay4kv55vDjry for <>; Mon, 4 Feb 2019 15:28:30 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:4864:20::342]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 6E56A12426E for <>; Mon, 4 Feb 2019 15:28:30 -0800 (PST)
Received: by with SMTP id 32so2788535ota.12 for <>; Mon, 04 Feb 2019 15:28:30 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=zzC+OMIoY4SrcgCOlAe7dPAgyqKKDFHgSm8pFa5h6+4=; b=Q8GhkG943ZqZF+y72Nh8LlgyX59QcIsSDoxl1zUIFW6ULfaWOOdR4G8K6Bdm1DMgbG 86akfTcr53+nVqNp3YaIfbHqdr+d5iwtarUlrFY+zPLsFgsdgx6I6asCElPNeEt/bRbH tfV/nxBWWVbMwiHY/qhmN1KXoy/IqikMSrdXwzXiTAtoNpwkO/G9zVVMyBjjfUnU/X9y 8e26v8tlrYTU+tUwNcX06K8wcpYGkPBEZOyP2Kgb+GcR0M3H2PXOcsBqx2X0gOUe3qlB Y2cJd5CvUlol6W+nasPwCyKkkO7sOWVlT4ukdRImePO8dQaWQbs12FkmYcyfPNsvyPLd ES4A==
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=zzC+OMIoY4SrcgCOlAe7dPAgyqKKDFHgSm8pFa5h6+4=; b=JPW75+/WbtuV39cT4Jfl+4FSvIBdrAN8NEFjMyqGgjtjXiww0edDVnsHCV8eObHHP4 01Qa7LdCXC20/9qQMN7C5HIgHeIWShakuM0ZSMaCYq9E+b21EQCSgO8sHYTd3qGG0joY t5VROLuHAIpxRYufiXEzDFSFC4M+yWgrwmo1BAlxStpi+UKgcXt4HZ3FWB6Z9+W+yZWg gfW0qB6aFtF8i1K4mKDdgdai1pUKCq4c+6uVtFulXSprY1bKdAGb0UHVbk4UgI80LlW3 hNclrnc8DDZmYaugKhhPrd2W6C/REOxzFKVSLIykJ16XNPHSBCUz3RXHyaDTM1ccdam4 dtBQ==
X-Gm-Message-State: AHQUAuaSU+HlhLDqUkBthmby6PrENoZMK6AA7ySNerwqnLiTs6I0Rd8v 1qO7VFeK8AiUP4djUjz3KpS5CKxmmML0Y5rI5jedxQQHLT0=
X-Google-Smtp-Source: AHgI3IZGs9Py/eEAqaeUO3bZekoatezZJ0Lwo5RwIVKbY1+x4gUxe/QBKIs/X+LbIjzIezAm5TcSAdLPetFIqaA3VKM=
X-Received: by 2002:aca:f18:: with SMTP id 24mr954338oip.310.1549322909651; Mon, 04 Feb 2019 15:28:29 -0800 (PST)
MIME-Version: 1.0
References: <> <>
In-Reply-To: <>
From: Richard Barnes <>
Date: Mon, 04 Feb 2019 18:28:11 -0500
Message-ID: <>
To: Tony Arcieri <>
Cc: CFRG <>
Content-Type: multipart/alternative; boundary="000000000000ac2dff058119d9c6"
Archived-At: <>
Subject: Re: [Cfrg] Curve25519 lacks private/public homomorphism?
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: Mon, 04 Feb 2019 23:28:33 -0000

Thanks, Tony.  In parallel, George Tankersley pointed me toward the
ristretto work as well.  There is an Internet-Draft now:

Given all this, seems like it could be something worthwhile for this group
to look at!


On Mon, Feb 4, 2019 at 6:23 PM Tony Arcieri <> wrote:

> On Mon, Feb 4, 2019 at 2:21 PM Richard Barnes <> wrote:
>> MLS has a case where it would be useful to be able to be able to
>> implement the following:
>> - Given a DH key pair whose private key is held by one set of parties and
>> public key by another
>> - Have a third party (holding only the public key) be able to generate a
>> "delta" such that:
>>   - The holders the private key can use the delta to update the private
>> key to a new value
>>   - The holders of the public key can use the delta to compute the
>> corresponding new public key
> That is, we're looking to use a certain homomorphism in the DH group
>> action that translates a change in private key to a change in public key.
>> For example, with traditional ECDH, you could generate a random number that
>> the private key holders could multiply with the private key, and the public
>> key holders could just do a DH operation to multiply the public key by the
>> delta.  (A sketch in Go here [1].)
> Welcome to the party!
> That is to say... this is a thorny problem which keeps coming up. The main
> thing you might want to look at for an immediate stopgap is Tor's new V3
> .onion addresses / hidden services design:
> There have been other schemes proposed to address this problem using
> blinding factors ala BIP32 non-hardened derivation. However those schemes
> ran afoul of the issue you describe below, despite multiple attempts to
> avoid it, and are vulnerable to key recovery attacks:
> The explosion of complexity that arises from attempting to handle low
> order points at the protocol level, even for such a comparatively simple
> protocol as this, is what initially lead me to discover Mike Hamburg's work
> on Decaf and vicariously the work of Henry de Valence et al on Ristretto:
>> When you try to do this with Curve25519 (or Curve448), however, you run
>> into a problem: `k_list[31] |= 64`.  The X25519 function in RFC 7748 [2]
>> ensures that the second-most-significant bit of a scalar private key is
>> always set, but this bit is not necessarily set in the product of two such
>> scalars.  In other words, there are scalars `ab` such that you can arrive
>> at `abG` as the result of a DH computation, but never abG will never be a
>> public key (since `X25519(ab, 9) != abG`).  The mapping from private keys
>> to public keys is not a homomorphism with regard to addition or
>> multiplication.
> This is at least colloquially referred to as "clamping", and yes, the
> complexity it glosses over is a huge problem for implementing more advanced
> protocols on top of Curve25519. Here's a thread with more background (oh my
> the cert is expired, how ironic):
>> This means we're out of luck with regard to our delta scheme.  If the
>> delta happens to result in a new private key with its penultimate bit
>> unset, then it can't actually be used as a private key -- and there's no
>> way for the delta-generating party to know this.
>> Is this surprising to people?  Is it a consequence of some property of
>> Curve25519 that is good for security, or is it just collateral damage?
> It's a fundamental tradeoff of Edwards curves (of your above options I'd
> call it "collateral damaged"). As Harry de Valence put it in a recent talk,
> "Edwards curves are simpler... but they push complexity upwards into the
> protocol".
> Some more discussion here (unfortunately this link isn't in
> Per the curve's creator, it's intended for simple protocols like D-H and
> signatures only.
> (Why does the penultimate bit need to be set?)
> My understanding is certain implementations of GF(2^255-19) field
> arithmetic (including some of the reference ones, I believe? I don't have a
> citation) as well as certain implementations of the Montgomery ladder
> require this bit to be set.
>> Do folks have other ideas for a "homomorphic" construction such as the
>> above that would accommodate this quirk of Curve25519?
> Ristretto elegantly solves these problems, and provides a prime order
> group abstraction which eliminates the incidental complexity of cofactors /
> low order groups which would otherwise get pushed into the protocol layer.
> I believe the balls are in motion to publish a draft soon which the CFRG
> can potentially select as a working group item.
> --
> Tony Arcieri