Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom

Johannes Merkle <> Thu, 16 January 2014 11:00 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 9617D1AE2A7 for <>; Thu, 16 Jan 2014 03:00:02 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -3.138
X-Spam-Status: No, score=-3.138 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.538] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id KfYcdnAQqfo3 for <>; Thu, 16 Jan 2014 03:00:00 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 497581AE07C for <>; Thu, 16 Jan 2014 02:59:59 -0800 (PST)
Received: from localhost (alg1 []) by (Postfix) with ESMTP id BC96D1A0087; Thu, 16 Jan 2014 11:59:45 +0100 (CET)
X-Virus-Scanned: by secunet
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with LMTP id aInzTIvH9uty; Thu, 16 Jan 2014 11:59:44 +0100 (CET)
Received: from mail-gw-int (unknown []) by (Postfix) with ESMTP id 00BBB1A0076; Thu, 16 Jan 2014 11:59:24 +0100 (CET)
Received: from [] (port=58332 by mail-gw-int with esmtp (Exim 4.80 #2 (Debian)) id 1W3kbJ-0007kM-Qu; Thu, 16 Jan 2014 11:55:05 +0100
Received: from [] ([]) by with Microsoft SMTPSVC(6.0.3790.4675); Thu, 16 Jan 2014 11:59:24 +0100
Message-ID: <>
Date: Thu, 16 Jan 2014 11:59:23 +0100
From: Johannes Merkle <>
User-Agent: Mozilla/5.0 (Windows NT 6.1; rv:24.0) Gecko/20100101 Thunderbird/24.2.0
MIME-Version: 1.0
To: David McGrew <>, Dan Brown <>
References: <> <> <> <> <> <>
In-Reply-To: <>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-OriginalArrivalTime: 16 Jan 2014 10:59:24.0096 (UTC) FILETIME=[042EF400:01CF12AA]
Cc: "''" <>
Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 16 Jan 2014 11:00:02 -0000

David McGrew schrieb am 16.01.2014 01:04:
> I think the advocates of "rigid" curves mean to highlight the fact that the rigid process can generate only a small
> number of curves. In contrast, when we are presented by a verifiably pseudorandom curve that was generated with an input
> seed of unknown provenance, it might be the case that many seeds were tested and rejected until one was found that
> generated a curve on which the DL problem could be solved more easily.   (Your model of "each curve has some probability
> of being vulnerable to an unknown attack" I think captures the concern, though one could generalize to a situation in
> which the expected running time of the DLP varied with the parameters.)
My understanding of Dan's reasoning is different. I think, the "unknown" in "probability of being vulnerable to an
unknown attack" relates to the entity generating the curve, i.e. NUTS captures the objective of generating curves in a
way that minimizes the "probability" that the curve may be or become vulnerably to attacks unknown by the party
generating the curve.

Of course, "probability" refers more to a "feeling in the guts" than to a (Bayesian) probability.

> Now, it would be possible to make a "rigid" process out of a pseudorandom process by using a seed value that nobody can
> control (say, the sha512 hash of SP500 prices on a given future date). Perhaps this is what you mean by PRF(NUMS) -> NUNS?

In retrospective this approach would be less convincing because some might still speculate that seed definition had been
specified at a later point of time, in spite of all evidence records.

And still, DJB could argue that the freedom in choices made for the derivation of the parameters, e.g. SHA-512, leaves
some questions unanswered, and he would probably label these curves (on the safecurve page) as being only "somewhat rigid".