Re: [Cfrg] Suggestion for open competition on PAKE -> Was Re: Dragonfly has advantages

Samuel Neves <sneves@dei.uc.pt> Sat, 04 January 2014 22:05 UTC

Return-Path: <sneves@dei.uc.pt>
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 461A51AE0A9 for <cfrg@ietfa.amsl.com>; Sat, 4 Jan 2014 14:05:57 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.16
X-Spam-Level: **
X-Spam-Status: No, score=2.16 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, GB_SUMOF=5, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-0.538, SPF_PASS=-0.001] autolearn=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 dpY8vNJuhBoW for <cfrg@ietfa.amsl.com>; Sat, 4 Jan 2014 14:05:55 -0800 (PST)
Received: from smtp2.dei.uc.pt (smtp2.dei.uc.pt [193.137.203.234]) by ietfa.amsl.com (Postfix) with ESMTP id 220F41AE00E for <cfrg@irtf.org>; Sat, 4 Jan 2014 14:05:54 -0800 (PST)
Received: from [192.168.1.64] (bl22-69-238.dsl.telepac.pt [2.83.69.238]) (authenticated bits=0) by smtp2.dei.uc.pt (8.14.4/8.14.4) with ESMTP id s04M5Mo7021725 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Sat, 4 Jan 2014 22:05:27 GMT
Message-ID: <52C885A5.9040900@dei.uc.pt>
Date: Sat, 04 Jan 2014 22:05:25 +0000
From: Samuel Neves <sneves@dei.uc.pt>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0
MIME-Version: 1.0
To: David Jacobson <dmjacobson@sbcglobal.net>
References: <CEED247E.2B845%paul@marvell.com> <CEEDD67B.22CC7%feng.hao@newcastle.ac.uk> <CAGZ8ZG293hO5HqB7khrcNUhw2x981jna+V3ivQNP3X8Btcp8OQ@mail.gmail.com> <52C8816A.1040104@sbcglobal.net>
In-Reply-To: <52C8816A.1040104@sbcglobal.net>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-FCTUC-DEI-SIC-MailScanner-Information: Please contact helpdesk@dei.uc.pt for more information
X-FCTUC-DEI-SIC-MailScanner-ID: s04M5Mo7021725
X-FCTUC-DEI-SIC-MailScanner: Found to be clean
X-FCTUC-DEI-SIC-MailScanner-SpamCheck: not spam, SpamAssassin (not cached, score=-60.25, required 3.252, autolearn=not spam, ALL_TRUSTED -10.00, BAYES_00 -0.25, L_SMTP_AUTH -50.00)
X-FCTUC-DEI-SIC-MailScanner-From: sneves@dei.uc.pt
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Suggestion for open competition on PAKE -> Was Re: Dragonfly has advantages
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, 04 Jan 2014 22:05:57 -0000

On 04-01-2014 21:47, David Jacobson wrote:
> On 1/4/14 9:18 AM, Trevor Perrin wrote:
>> Another important issue, particularly for EC protocols, is to
>> distinguish operations with a fixed base (or fixed point) from
>> operations with a random base / point. The fixed operations can be
>> optimized to be several times faster (perhaps ~4x is a rule of thumb
>> I've heard).
> This seems strange to me, and I've implemented ECC several times over
> the last decade.   I think you might have meant that implementations
> using special modulii that can be written as  the sum of  +/- 1 at
> selected word boundaries or as 2^n - k for some small k are several
> times faster than implementations written to support arbitrary moduli.

Fixed base lets you precompute arbitrary multiples of G offline. For
example, if you compute {0..16} G, 2^4 * {0..16} G, 2^(4i) {0..16} G,
..., you only need to perform around log2(exponent)/4 online group
operations. Doing this safely against side-channel attacks requires some
care, of  course.