Re: [CFRG] compact representation and HPKE

Loup Vaillant-David <> Wed, 10 February 2021 23:12 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 2B4DF3A0D63 for <>; Wed, 10 Feb 2021 15:12:08 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.918
X-Spam-Status: No, score=-1.918 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id aPgyPmXGkK7z for <>; Wed, 10 Feb 2021 15:12:06 -0800 (PST)
Received: from ( []) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 401253A0D62 for <>; Wed, 10 Feb 2021 15:12:05 -0800 (PST)
Received: from grey-fade (unknown []) (Authenticated sender: by (Postfix) with ESMTPSA id 4A0F8240005; Wed, 10 Feb 2021 23:12:00 +0000 (UTC)
Message-ID: <>
From: Loup Vaillant-David <>
To: Dan Harkins <>,
Date: Thu, 11 Feb 2021 00:11:59 +0100
In-Reply-To: <>
References: <> <> <> <> <> <> <> <> <>
Content-Type: text/plain; charset="UTF-8"
X-Mailer: Evolution 3.28.5-0ubuntu0.18.04.2
Mime-Version: 1.0
Content-Transfer-Encoding: 7bit
Archived-At: <>
Subject: Re: [CFRG] compact representation and HPKE
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: Wed, 10 Feb 2021 23:12:08 -0000

On Wed, 2021-02-10 at 04:42 -0800, Dan Harkins wrote:
> For all of these curves, p = 3 mod 4 so doing a modular square root
> is just exponentiation to (p + 1)/4. Not sure how onerous an
> additional exponentiation is.

I've just checked by removing the final inversion from my X25519
implementation (which uses an x-only ladder), the cost is less than
10%. Comparatively even less if you're using a more expensive ladder.

> But then Mike Hamburg was saying that one can do a x-only Montgomery
> Ladder for these curves if an exponentiation is, indeed, onerous so
> there are options to consider.

To be checked, but an x-only ladder is likely to be faster on its own.
So not only do you gain speed by avoiding an exponentiation, you gain
speed by running a faster ladder.

While we *may* beat x-only ladders by using a complete addition law and
fixed windows, it would be more complex, and require more memory (stack
in most implementations). And a naive x-y ladder is about half the
speed of the x-only ladder, if not less (assuming constant time
implementations). This is horrible for embedded applications.

Alternatively, we could recover the y-coordinate *after* performing an
x-only ladder. With luck, it might not even cost an additional
exponentiation. Still, this feels like an avoidable complication, not
worth the single bit of security you could get by recovering the sign
of a point.

As an implementer, I have a very strong preference for x-only ladders:
not only are they fast, they're easiest to implement. Less room for