Re: What is "verifiably at random"??? (Was RE: I-D Action:draft-ietf-pkix-ecc-subpubkeyinfo-00.txt)

[Bodo Moeller <bmoeller@xxxxxxx>]

On Sun, Dec 16, 2007 at 03:47:01PM -0500, Turner, Sean P. wrote:

>> From: owner-ietf-pkix@xxxxxxxxxxxx 
>> [mailto:owner-ietf-pkix@xxxxxxxxxxxx] On Behalf Of Kemp, David P.
>> Sent: Thursday, December 06, 2007 1:28 PM
>> To: ietf-pkix@xxxxxxx
>> Subject: What is "verifiably at random"??? (Was RE: I-D 
>> Action:draft-ietf-pkix-ecc-subpubkeyinfo-00.txt)

>> Section 2.1.1.2.1 of the new ECC I-D states:
>> 
>>    If version is ecdpVer2, then the curve and the base point
>>    G shall be generated verifiably at random, and curve.seed
>>    shall be present.
>> 
>> It seems quite peculiar to say that a value is generated "at random"
>> when the value has zero entropy (as is the case when a curve 
>> and base point are generated by hashing a seed and the value 
>> of the seed is known).  That's almost as peculiar as claiming 
>> that the well known constant PI is random.
[...]
>> Please replace the phrase "generated verifiably at random" 
>> with something like "generated deterministically" that does 
>> not imply that there is some entropy/unpredictability involved 
>> in the process.

> Thanks for the review. The phrase you refer to actually appears more than
> once. I'll replace it in all places as suggested.

The phrase "verifiably at random" certainly is incorrect here and
"generated deterministically" arguably is correct.  However, the
latter isn't quite meaningful as it is not really saying what this is
supposed to say -- it misses the key idea.  The best way I know to
express the concept is saying that the values have been generated
"verifiably pseudorandomly".

We use a standardized procedure involving cryptographic hashes to
deterministically generate the values from a seed string so that
others can verify that the values have been generated properly.  They
may not be able to verify how we chose the seed, but still they have
some assurance that there is no hidden trapdoor, and more generally
that anything that is wrong with the particular value also is wrong
with a non-negligible fraction even of actually random values (thanks
to the assumed pseudorandomness of hash outputs).

Values that have been "generated deterministically" might have been
deterministically constructed specifically to contain a trapdoor;
at least, the term isn't saying anything to the contrary.  When
speaking of "verifiably pseudorandom" values, we stress that these
values are, in some sense, similar to random values (even though of
course they certainly are not actually random).

Bodo