Re: [Cfrg] How to (pre-)compute a ladder [revised version]

Antonio Sanso <asanso@adobe.com> Fri, 23 June 2017 07:07 UTC

Return-Path: <asanso@adobe.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 9647B129C32 for <cfrg@ietfa.amsl.com>; Fri, 23 Jun 2017 00:07:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.021
X-Spam-Level:
X-Spam-Status: No, score=-2.021 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=adobe.com
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 Ff6yZQ89MGzv for <cfrg@ietfa.amsl.com>; Fri, 23 Jun 2017 00:07:16 -0700 (PDT)
Received: from NAM02-SN1-obe.outbound.protection.outlook.com (mail-sn1nam02on0074.outbound.protection.outlook.com [104.47.36.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id F2C1F1200CF for <cfrg@irtf.org>; Fri, 23 Jun 2017 00:07:15 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adobe.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=NCzQirTQ8pQ1Zln3gE8VWtfhmTSrjTtwkoZnOqvWSng=; b=YcEf1fzWzpQTUT81TiUqYirC1olanLvaeM8PQ6ecQ8pghRBhBK0ZHh8Zu/BVNB00Ugg98LaeRRDV0ahGueY5LuFBcSt4v2Bbtud1OijimbQaEq0CQ/nLU7Hqsjis/Oy+Psy+G4zRVj9P9hdsvLHsU7Ft316adZyPbdJAyfiPqAo=
Received: from BLUPR0201MB1585.namprd02.prod.outlook.com (10.163.120.140) by BLUPR0201MB1585.namprd02.prod.outlook.com (10.163.120.140) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1178.14; Fri, 23 Jun 2017 07:07:13 +0000
Received: from BLUPR0201MB1585.namprd02.prod.outlook.com ([10.163.120.140]) by BLUPR0201MB1585.namprd02.prod.outlook.com ([10.163.120.140]) with mapi id 15.01.1178.023; Fri, 23 Jun 2017 07:07:13 +0000
From: Antonio Sanso <asanso@adobe.com>
To: Peter Dettman <peter.dettman@bouncycastle.org>
CC: Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx>, "cfrg@irtf.org" <cfrg@irtf.org>, =?Windows-1252?Q?Julio_C=E9sar_Lopez?= <jlopez@ic.unicamp.br>, Thomaz Oliveira <thomaz.figueiredo@gmail.com>, "huseyin.hisil@yasar.edu.tr" <huseyin.hisil@yasar.edu.tr>
Thread-Topic: [Cfrg] How to (pre-)compute a ladder [revised version]
Thread-Index: AQHSyrVtu4VVdn8k90q2mdRQReJ0C6InJRYAgAskMgA=
Date: Fri, 23 Jun 2017 07:07:13 +0000
Message-ID: <F694544B-5D56-458C-AA65-3F756AA0CE02@adobe.com>
References: <CAHOTMVKHA-yJR1oCyPtUp4-aJVc3dTdyxQHNo4xqnJt0hU6jVQ@mail.gmail.com> <CAMm+Lwgm8XzTBarZ1eFePTZGORorBJAeF7brDkhWGQKQVT0LPQ@mail.gmail.com> <CAMm+LwggT_AVv=KjzM1r=6UnkeK+g8zkticXFBDQ0cUXs_PP0A@mail.gmail.com> <CAHOTMVLHPFyi2VWpv85hrZ1MoXqeHYUv52wkMxjj3xp5B4V1cw@mail.gmail.com> <CAMm+Lwgfk1=yEJSbZbaZLvF5k5k66VVSx6MzKLM+DbUV7Ls6Xw@mail.gmail.com> <CAHOTMVK1gYrFiwd8f8zf2zPXYyCorp+jixkcY5FLhfHfv0NkWw@mail.gmail.com> <CAMm+LwjeZdR=ZGX0topN2w6P12jEmR-TQ8M9+anyETj43nbiqg@mail.gmail.com> <CAHOTMVL2e2UjVX6VKgHUbOHrb-gsU8kn_cxY1FdNrnj29cki9g@mail.gmail.com> <alpine.LFD.2.02.1703291804030.8996@delta.cs.cinvestav.mx> <alpine.LFD.2.02.1705111858040.25089@delta.cs.cinvestav.mx> <02899a12-8cf7-c318-32ea-9491ec2a22c2@bouncycastle.org>
In-Reply-To: <02899a12-8cf7-c318-32ea-9491ec2a22c2@bouncycastle.org>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: bouncycastle.org; dkim=none (message not signed) header.d=none; bouncycastle.org; dmarc=none action=none header.from=adobe.com;
x-originating-ip: [192.147.117.11]
x-ms-publictraffictype: Email
x-microsoft-exchange-diagnostics: 1; BLUPR0201MB1585; 7:UgCheSLSqY2KLoEs0YmRufMo10S6DX+Km/hJtJtuoeykUykd7AheV0LH4O02+tHhz6YQbnNU//P9PQ0G6wwC0BLIgJSizFl4vxwC0D6f5aZIHQ9gfJ5fDQCLbyl2hdEP5CPzk5iaKITTqbTDvBnnHTtdvksKxFEFy1QPI0NIne210xczxC1oDSLyKBZGCJcjX1O6e3XpDda8GeZ4z7oRpCDFIwhEYoq+s8BRB/unmoXlkJasHzsuM5bIQxz7R/emFN24tllbfXguJeEDzL8cWM7exnQP0BndG7xqfvzgklhYU+ERlhpVYewQY8AEj9UF+mz2a9BUXnuuAt06hh0oNKBqr/UXb7uUuJbZtOL0czviDHQr5vVm9U8HkyLrkYSNu6ts5rBW4pC1TDUHCVIR4Uyc6aXb74g+qq+WPqDtdCQbGY+oPvbzBg2kq3JWgoulVFT++6X4B61hffb5S/+PDypwaka4ym+SKOQO5V6Cf1ycng/Cgb9bv2T0tw5hK9iawWr6ddVPGiQzxwRabUKja4rdeKQOSh2f5ZbsR7MCxnBkmGshVuuCleg0+J4Bu1+xgKhAFCXvVrVmsSAlyQc+/RO02ReLTXWawTa5uQn8Vf/dJHD1ShyVi9sFREWLzIedtjSN+RVKEQVGUlqk+bna/cR2zHobzCSJbyzQXZtmBNSEumStetksLH6Ukr4Qi0V/E5khHgZxCUCijh5KjJSsp2guPsL/fL0fD7BtdDHol2O7PTOB8BCuU0L2k1U//ssjVvwBnSxNEsIOoDbfs8w4T3z9mJjkCFgMQ+cTl/rJHRY=
x-ms-office365-filtering-correlation-id: 3e00fb1b-6269-4bbd-f6d4-08d4ba06793f
x-ms-office365-filtering-ht: Tenant
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(2017030254075)(48565401081)(201703131423075)(201703031133081)(201702281549075); SRVR:BLUPR0201MB1585;
x-ms-traffictypediagnostic: BLUPR0201MB1585:
x-microsoft-antispam-prvs: <BLUPR0201MB1585429A9B1EF9CAFCCE8983D9D80@BLUPR0201MB1585.namprd02.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:;
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(61425038)(6040450)(601004)(2401047)(8121501046)(5005006)(10201501046)(100000703101)(100105400095)(93006095)(93001095)(3002001)(6055026)(61426038)(61427038)(6041248)(20161123560025)(20161123555025)(20161123564025)(20161123562025)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(20161123558100)(6072148)(100000704101)(100105200095)(100000705101)(100105500095); SRVR:BLUPR0201MB1585; BCL:0; PCL:0; RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095); SRVR:BLUPR0201MB1585;
x-forefront-prvs: 0347410860
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(39850400002)(39840400002)(39860400002)(39400400002)(39410400002)(39450400003)(24454002)(377454003)(83716003)(10090500001)(2906002)(50986999)(54356999)(76176999)(3846002)(229853002)(38730400002)(110136004)(7736002)(53936002)(561944003)(478600001)(39060400002)(6116002)(102836003)(122556002)(2900100001)(33656002)(6916009)(8676002)(6436002)(2950100002)(81166006)(3280700002)(6246003)(25786009)(53546010)(3660700001)(66066001)(36756003)(86362001)(305945005)(5660300001)(6506006)(4326008)(6306002)(6512007)(966005)(54906002)(189998001)(14454004)(8936002)(6486002)(99286003)(77096006)(82746002)(93886004); DIR:OUT; SFP:1101; SCL:1; SRVR:BLUPR0201MB1585; H:BLUPR0201MB1585.namprd02.prod.outlook.com; FPR:; SPF:None; MLV:ovrnspm; PTR:InfoNoRecords; LANG:en;
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="Windows-1252"
Content-ID: <B226D7FF7FDEE243A47505115235C541@namprd02.prod.outlook.com>
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: adobe.com
X-MS-Exchange-CrossTenant-originalarrivaltime: 23 Jun 2017 07:07:13.1793 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: fa7b1b5a-7b34-4387-94ae-d2c178decee1
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BLUPR0201MB1585
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/hxgFdqb55kqq5wWBpTKQueVkLzo>
Subject: Re: [Cfrg] How to (pre-)compute a ladder [revised version]
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: Fri, 23 Jun 2017 07:07:19 -0000

hi Peter
On Jun 16, 2017, at 6:58 AM, Peter Dettman <peter.dettman@bouncycastle.org> wrote:

> Hi Francisco,
> 
> I've updated my (java) implementations of X25519 and X448 in line with
> your revised paper.

out of curiosity is this a public repo I can look at ? :)

regards

antonio

> My rough benchmark results for a complete ECDH are
> -17.7% and -19.5% time required for X25519 and X448 respectively.
> 
> These are perhaps slightly more modest than the paper's estimates. Your
> paper already anticipates that (uncounted) field add/sub are significant
> in practice.
> 
> Part of the difference however is that my implementation of Algorithm 3
> handles the final 'q' bits using simple doublings, and removes redundant
> cswaps - just as Algorithm 5 does. Of course Alg. 3 is just as presented
> in RFC 7748, but it might be a fairer comparison to first apply to Alg.
> 3 those of your optimizations that are applicable.
> 
> Also, my (32-bit) X448 implementation (Alg. 5) required a carry
> propagation for 'A' (line 10), due to tight bounds on limbs when
> squaring D, E. I did the same for (32-bit) X25519 although I haven't yet
> proved it necessary.
> 
> An idea: for fixed-base X25519, why not precompute one doubling? i.e.
> just calculate (k/2) * 2P, needing only 2 final doublings (you even
> already have S of order 4). I am not sure whether this extends to
> precomputing (q-1) doublings.
> 
> Another thought that occurred to me is that someone might get the idea
> to use your fixed-base ladder with some other point. Couldn't this go
> awry if that point were already "P + S" or similar? If so, a caution
> somewhere in the paper on preconditions for the fixed point might be
> advised.
> 
> Regards,
> Pete Dettman
> 
> 
> On 12/05/2017 7:14 AM, Francisco Rodriguez- Henriquez wrote:
>> Dear CFRG community,
>> 
>> We would like to draw your attention to an improved version of our IACR
>> pre-print 2017/264 now entitled:
>> 
>>    "How to (pre-)compute a ladder"
>> 
>> In this revised version, we present an improved differential addition
>> formula that uses pre-computation to match the computational cost of the
>> classical Montgomery differential addition.
>> 
>> Accordingly, our estimates suggest that a full implementation of our
>> pre-computable ladder proposal should outperform state-of-the-art
>> software implementations of the X25519 and X448 functions by a 40%
>> speedup when working in the fixed-point scenario.
>> 
>> We would be delighted to receive feedback (including sightings of typos)
>> from the CFRG community.
>> 
>> With best regards,
>> 
>> Thomaz Oliveira, Julio López, Hüseyin Hisil and Francisco
>> Rodríguez-Henríquez
>> 
>> 
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>> 
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg