Re: [Cfrg] How to (pre-)compute a ladder [revised version]
Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx> Fri, 14 July 2017 19:54 UTC
Return-Path: <francisco@cs.cinvestav.mx>
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 A639E131937 for <cfrg@ietfa.amsl.com>; Fri, 14 Jul 2017 12:54:44 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.903
X-Spam-Level:
X-Spam-Status: No, score=-1.903 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-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 iTnZ2tX1umT2 for <cfrg@ietfa.amsl.com>; Fri, 14 Jul 2017 12:54:43 -0700 (PDT)
Received: from delta.cs.cinvestav.mx (delta.cs.cinvestav.mx [148.247.102.21]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 1EE3413193F for <cfrg@irtf.org>; Fri, 14 Jul 2017 12:54:43 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by delta.cs.cinvestav.mx (Postfix) with ESMTP id 144735C13CA; Fri, 14 Jul 2017 14:54:28 -0500 (CDT)
X-Virus-Scanned: amavisd-new at cs.cinvestav.mx
Received: from delta.cs.cinvestav.mx ([127.0.0.1]) by localhost (delta.cs.cinvestav.mx [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ARCYpgCEAkqt; Fri, 14 Jul 2017 14:54:26 -0500 (CDT)
Received: by delta.cs.cinvestav.mx (Postfix, from userid 1507) id 997265C1526; Fri, 14 Jul 2017 14:54:26 -0500 (CDT)
Received: from localhost (localhost [127.0.0.1]) by delta.cs.cinvestav.mx (Postfix) with ESMTP id 869F75C13CA; Fri, 14 Jul 2017 14:54:26 -0500 (CDT)
Date: Fri, 14 Jul 2017 14:54:26 -0500
From: Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx>
To: Mike Hamburg <mike@shiftleft.org>
cc: "cfrg@irtf.org" <cfrg@irtf.org>, Julio César Lopez <jlopez@ic.unicamp.br>, Thomaz Oliveira <thomaz.figueiredo@gmail.com>, huseyin.hisil@yasar.edu.tr, Armando Faz <armfazh@gmail.com>
In-Reply-To: <alpine.LFD.2.02.1707141329090.16576@delta.cs.cinvestav.mx>
Message-ID: <alpine.LFD.2.02.1707141441220.17686@delta.cs.cinvestav.mx>
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> <alpine.LFD.2.02.1707141329090.16576@delta.cs.cinvestav.mx>
User-Agent: Alpine 2.02 (LFD 1266 2009-07-14)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; format="flowed"; charset="US-ASCII"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/_1o0eT25xGtQujRdJLuURjZbA9g>
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, 14 Jul 2017 19:54:45 -0000
On May 12, 2017, at 2:15 PM, Mike Hamburg <mike@shiftleft.org> wrote: > Hello Francisco et al, > This is a clever and useful piece of work. It's a good intermediate > between just using the standard Montgomery ladder for everything, and > going to a full Edwards implementation with combs or something. It > especially seems useful where power analysis resistance is required, > because other precomputation methods usually aren't suitable. The RTL > Montgomery ladder (or Joye double-add ladder) is already known to be > useful in this situation, at least with some modification to prevent > coordinates from staying the same between iterations. Since you're > speeding up the RTL Montgomery ladder, your optimization can slot right > in to some implementations. Hi Mike, Thanks for your comments and sorry for this really slow reply :) I agree with you about the fact that the RTL Montgomery ladder by Joye was already known for performing this feature. > You should probably compare to existing Edwards precomputation methods > in your paper, since they are the likely alternative to your technique. > In particular, I noticed that you compared against the EBACS version of > Ed448-Goldilocks. With a fixed base point, your method uses 41% less > time for the Montgomery ladder with a 25kiB table. However, the EBACS > version of Ed448-Goldilocks doesn't use the Montgomery ladder for > fixed-base scalarmul. Instead it uses a combs algorithm, which uses a > 15kiB table and takes about 70% less time than the Montgomery ladder; > see https://bench.cr.yp.to/results-dh.html. Libdecaf likewise uses > precomputed combs for fixed-base scalarmul. But your new technique is > certainly simpler. I agree with you, there are faster methods to perform pre-computation, which offer [some] protection against side-channel attacks. In our work, we were specifically targeting the RFC 7748 Memo, and hence we only meant to compare against ladder procedures for computing the scalar multiplication. I believe that the tradeoffs between the simplicity/elegance/beauty of the ladders Vs. the efficiency of regular recoding + other methods of pre-computation, was already debated in this list :) Cheers, Francisco > Cheers, > -- Mike
- [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Aaron Zauner
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Dmitry Khovratovich
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Nadim Kobeissi
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Taylor R Campbell
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- [Cfrg] A note on how to (pre-)compute a ladder Francisco Rodriguez- Henriquez
- Re: [Cfrg] A note on how to (pre-)compute a ladder Peter Dettman
- Re: [Cfrg] A note on how to (pre-)compute a ladder Peter Dettman
- Re: [Cfrg] A note on how to (pre-)compute a ladder Francisco Rodriguez- Henriquez
- Re: [Cfrg] A note on how to (pre-)compute a ladder Francisco Rodriguez- Henriquez
- [Cfrg] How to (pre-)compute a ladder [revised ver… Francisco Rodriguez- Henriquez
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Mike Hamburg
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Peter Dettman
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Antonio Sanso
- Re: [Cfrg] How to (pre-)compute a ladder [full C … Francisco Rodriguez- Henriquez
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Francisco Rodriguez- Henriquez
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Francisco Rodriguez- Henriquez