Re: [Cfrg] ECC mod 8^91+5

Dan Brown <danibrown@blackberry.com> Wed, 02 August 2017 16:04 UTC

Return-Path: <danibrown@blackberry.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 17898132143 for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 09:04:52 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.601
X-Spam-Level:
X-Spam-Status: No, score=-2.601 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham 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 zHXKQQliUdLY for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 09:04:50 -0700 (PDT)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) (using TLSv1.2 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 4CCDB129B03 for <cfrg@irtf.org>; Wed, 2 Aug 2017 09:04:49 -0700 (PDT)
Received: from xct102cnc.rim.net ([10.65.161.202]) by mhs214cnc.rim.net with ESMTP/TLS/DHE-RSA-AES256-SHA; 02 Aug 2017 12:04:43 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT102CNC.rim.net ([fe80::2066:5d4f:8c45:af55%17]) with mapi id 14.03.0319.002; Wed, 2 Aug 2017 12:04:43 -0400
From: Dan Brown <danibrown@blackberry.com>
To: "D. J. Bernstein" <djb@cr.yp.to>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] ECC mod 8^91+5
Thread-Index: AdLNjx77PpyZT1/ZSIWijHcZu9CKCQ9d+upAACBlnYAADxVWAAAHoxmA
Date: Wed, 02 Aug 2017 16:04:42 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF501B79B1B@XMB116CNC.rim.net>
References: <20170802081237.k6pcmldfso4dkgeq@LK-Perkele-VII> <20170802152430.8449.qmail@cr.yp.to>
In-Reply-To: <20170802152430.8449.qmail@cr.yp.to>
Accept-Language: en-US, en-CA
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.249]
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/zbUXaKnCBQvHS_NF7IA0lE-4uRs>
Subject: Re: [Cfrg] ECC mod 8^91+5
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
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, 02 Aug 2017 16:04:52 -0000

Hi Dan,

Thanks so much for clarifying this!  

Sorry to all in CFRG that I am not up to speed on ECC implementation security and efficiency.

Just to be clear: this proposed special curve 2y^2=x^3+x (over GF(8^91+5)) is not intended to meet all SafeCurves requirements (as I remember them).  In particular and especially, (a) it is not twist-secure, and (b) it has a special feature of an efficient (complex) endomorphism.

Best regards,

Dan

Dumb question (on efficiency): For plain old Diffie--Hellman, is it right that Edwards form (8M per op) is only better than Montgomery (9M per bit) if a large window is used (to reduce ops/bit to something close to 1)?  If so, is this deemed simpler?  I guess where I'm going with this, is that Edwards form is very exciting from a research perspective, but maybe (0.000001% sure) it is not ready and ideal for engineering.  Again, I'm probably just totally missing something.

-----Original Message-----
From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of D. J. Bernstein
Sent: Wednesday, August 2, 2017 11:25 AM
To: cfrg@irtf.org
Subject: Re: [Cfrg] ECC mod 8^91+5

Ilari Liusvaara writes:
> Unfortunately there is another related problem: The theorem that says 
> that folded Montgomery ladder always works assumes that there is 
> unique point of order 2.

The theorem in the Curve25519 paper assumed a unique point of order 2, but this turned out to be unnecessary. See Theorem 4.5 in

   https://cr.yp.to/papers.html#montladder

and in particular the proofs of the underlying DBL and DADD theorems via the Edwards addition law. The paper also gives proofs from the historical Weierstrass perspective.

The completeness issue is more problematic outside the ladder context:

   * The fast complete Edwards formulas don't apply to this curve: the
     curve doesn't have a unique point of order 2.

   * The fast complete Hessian formulas also don't apply to this curve:
     the curve doesn't have a unique point of order 3.

   * The formulas from https://cr.yp.to/talks/2009.07.17/slides.pdf and
     https://eprint.iacr.org/2015/1060 do apply but don't meet the
     SafeCurves requirements of speed and simplicity ("implementations
     of scalar multiplication for the same curve cannot be much faster"
     and "reasonably fast implementations of scalar multiplication for
     the same curve cannot be much more concise"), so implementors are
     pressured to use incomplete formulas instead.

---Dan

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg