[Cfrg] ed448goldilocks vs. numsp384t1 and numsp512t1

"D. J. Bernstein" <djb@cr.yp.to> Sat, 18 October 2014 20:30 UTC

Return-Path: <djb-dsn2-1406711340.7506@cr.yp.to>
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 20D521A066C for <cfrg@ietfa.amsl.com>; Sat, 18 Oct 2014 13:30:32 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.101
X-Spam-Level:
X-Spam-Status: No, score=0.101 tagged_above=-999 required=5 tests=[BAYES_50=0.8, RCVD_IN_DNSWL_LOW=-0.7, UNPARSEABLE_RELAY=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 Km3Vkmeb4-bG for <cfrg@ietfa.amsl.com>; Sat, 18 Oct 2014 13:30:29 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id E29441A036B for <cfrg@irtf.org>; Sat, 18 Oct 2014 13:30:27 -0700 (PDT)
Received: (qmail 818 invoked by uid 1011); 18 Oct 2014 20:30:24 -0000
Received: from unknown (unknown) by unknown with QMTP; 18 Oct 2014 20:30:24 -0000
Received: (qmail 23025 invoked by uid 1001); 18 Oct 2014 20:30:17 -0000
Date: 18 Oct 2014 20:30:17 -0000
Message-ID: <20141018203017.23023.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@irtf.org
Mail-Followup-To: cfrg@irtf.org
In-Reply-To: <ACC414D4-6651-42C7-B0EF-8E381EE9A0B9@shiftleft.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/XcszWmrTsQZXCxEyCnAEsuA9P-w
Subject: [Cfrg] ed448goldilocks vs. numsp384t1 and numsp512t1
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: Sat, 18 Oct 2014 20:30:32 -0000

Michael Hamburg writes:
> I didn’t do this last time, which is (part of?) why the numbers from
> my own benchmarks do not match DJB’s numbers; see below.

Numbers are now coming into eBATS (see http://bench.cr.yp.to) for Mike's
fixed ed448goldilocks software, and confirm what Mike said about speed
compared to Microsoft's claimed speed. Here's the updated comparison
chart on Sandy Bridge, the microarchitecture selected by Microsoft for
benchmarks in http://eprint.iacr.org/2014/130.pdf:

    617000 cycles claimed: numsp384t1 (ed-384-mers),    ~2^192 security.
    666544 cycles measured on h6sandy: ed448goldilocks, ~2^224 security.
   1293000 cycles claimed: numsp512t1 (ed-512-mers),    ~2^256 security.

These DH ratios don't _perfectly_ predict ratios for other operations---
the instruction mix changes, and speeds of other operations depend on
choices of precomputed table size---but at this point it's unsurprising
to see ed448goldilocks close to numsp384t1 for signature generation:

    231000 cycles claimed: numsp384t1 (ed-384-mers),    ~2^192 security.
    234844 cycles measured on h6sandy: ed448goldilocks, ~2^224 security.
    446000 cycles claimed: numsp512t1 (ed-512-mers),    ~2^256 security.

Also signature verification:

    624000 cycles claimed: numsp384t1 (ed-384-mers),    ~2^192 security.
    729152 cycles measured on h6sandy: ed448goldilocks, ~2^224 security.
   1320000 cycles claimed: numsp512t1 (ed-512-mers),    ~2^256 security.

Microsoft says that its goal is to justify "all choices" in NUMS with
"undisputable efficiency arguments"; but the actual measurements show
considerably better efficiency/security tradeoffs for other curves.
There's a lot more wiggle room for achieving not-quite-the-best speeds
than there is for achieving the best speeds.

---Dan