Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base

Watson Ladd <watsonbladd@gmail.com> Thu, 22 January 2015 01:39 UTC

Return-Path: <watsonbladd@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B44581A1AA6 for <cfrg@ietfa.amsl.com>; Wed, 21 Jan 2015 17:39:23 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 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, SPF_PASS=-0.001] autolearn=ham
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 LexwBTqGcMz5 for <cfrg@ietfa.amsl.com>; Wed, 21 Jan 2015 17:39:21 -0800 (PST)
Received: from mail-yk0-x235.google.com (mail-yk0-x235.google.com [IPv6:2607:f8b0:4002:c07::235]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6D0B21A1A25 for <cfrg@irtf.org>; Wed, 21 Jan 2015 17:39:21 -0800 (PST)
Received: by mail-yk0-f181.google.com with SMTP id 79so8036072ykr.12 for <cfrg@irtf.org>; Wed, 21 Jan 2015 17:39:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=3VvlyWVML1e0FcvZM2s5DRYkj+oEF+TXdOqjaxC1sWA=; b=UOysQ+hCgsOq6VWpxr4CFC12fxJj7k7XWMVebbjNFZeMOfoEzf3eZSIl2JcLJ0ZgTE vU/cvnD4oypUBiaAhMuOUUoZeA8TlYy+BkXt0pqH+s9kdfAmcw41a7SJPcPD2Hl+vNNG UUTgGBaB1GxiF2Zn0SOR9UOYEFhRLsgrFWBpM9eoOWytJULazHiHH/mLA1YIWMmNZ2Xt t7pspYOLuDaZWEpfHlbcXUu4twhma56b1pyqGmnllsE/xfAP0mv3vW2ar6uzt8lHk9uL TmG9wToVeByFAEqT5Pk3++PnMKuRgR8OtC4z0FB9VvDn74GAuOBwQzzqpj6jI5wZjtmL 38SQ==
MIME-Version: 1.0
X-Received: by 10.170.217.9 with SMTP id j9mr16310922ykf.19.1421890760700; Wed, 21 Jan 2015 17:39:20 -0800 (PST)
Received: by 10.170.115.77 with HTTP; Wed, 21 Jan 2015 17:39:20 -0800 (PST)
In-Reply-To: <54BF6B8C.2020707@brainhub.org>
References: <54AA4AB9.70505@brainhub.org> <54B315CA.6040900@brainhub.org> <88805D27-3B08-421D-B62A-2FC61AC5851A@shiftleft.org> <CACsn0c=qxBXCkr7hCtzgY9U+5_N8hY=jShU7g=hUbqkrUMYxNw@mail.gmail.com> <3C94ED57-5089-4A6D-9CC6-2DCD452C7BCF@shiftleft.org> <CACsn0ck6q9nxioS7q66MkB6M+YmaGj=Nmqop1LQ-DuG0q78GaQ@mail.gmail.com> <54BCAE24.6020408@brainhub.org> <CACsn0ckb6t_bsAocYnBhiqRkaJ3HExF4QNDf83riQqc=uHdQ0A@mail.gmail.com> <54BF6B8C.2020707@brainhub.org>
Date: Wed, 21 Jan 2015 17:39:20 -0800
Message-ID: <CACsn0cn9vT8QnaKhZx5LQ1FSjRyagOzHDnW9Ub=xvV93E4EBJw@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Andrey Jivsov <crypto@brainhub.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/vNsWjbf1paJwhnhHN01yjfdEriE>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 22 Jan 2015 01:39:23 -0000

On Wed, Jan 21, 2015 at 1:04 AM, Andrey Jivsov <crypto@brainhub.org> wrote:
> On 01/19/2015 04:20 PM, Watson Ladd wrote:
>>
>> And once again, the Montgomery ladder is extremely small in codesize,
>> one the field operations are implemented. Or is there some other
>> benefit I don't understand you are thinking of?
>
>
> The benefits of using extended twisted Edwards coordinates would be:
>
> * An order of magnitude faster key generation (this is a part of signature
> generation or ECDH ephemeral key generation)
> * Ability to add points (needed for signatures and many other protocols)
> * The same code can do what Montgomery ladder does (variable case
> scalarmult) at the same speed.
>
> It plausible that a library that needs more then ECDH variable base
> scalarmult would implement the above operations without the Montgomery
> ladder.
>
> However, if there there is a penalty to recover 'y', that unified
> implementation is less likely to happen.

And the cost here is what? Note that your first bullet point is false:
the comb method on twisted Edwards can deliver a point on a Montgomery
curve, with minimal change in performance. I agree we would be using
twisted Edwards for signatures and protocols that require addition
(although Mike Hamburg has some ideas on safer point formats, based on
Jacobi quartics). But that doesn't mean we should use the same method
for ECDH: there are security advantages which your proposal doesn't
have.

Once again this got discussed extensively over the summer.

Sincerely,
Watson Ladd