[Cryptography] ideas for (long) Nothing up my sleeve numbers

John Denker jsd at av8n.com
Sun Mar 30 17:26:41 EDT 2014

On 03/30/2014 01:41 PM, Viktor Dukhovni wrote:

> There is no such thing as a "random constant", let alone a provably
> random constant.  A value is either constant (0 entropy) or is
> selected "at random" from a finite set of values via a probability
> distribution with more than 0 bits of entropy. 

Bravo.  That is very true and very important.

Let me repeat:  There is no such thing as a random number.
If it's a number, it's not random.
If it's random, it's not a number.
You can have a random distribution over numbers, but then
the randomness is in the distribution, not in any particular
number that may have been drawn from the distribution.

A so-called RNG is a random generator of numbers, not a
generator of random numbers.


Now, to answer the question that was originally asked:  Here
is how to collect N bits with the nothing-up-my-sleeve property:

Organize several players who will each contribute a string
of N bits:  One string from the NSA, one from the Chinese
equivalent, one from the Russians, one from Google, one from
EFF, et cetera.  We are going to XOR the strings, so you
don't need to trust all of these players;  it suffices to
convince yourself that at least /one/ of them will see it
in his best interest to contribute a good number.

During phase 1, each player selects a N-bit number.  IMHO 
the minimax strategy is to draw the number from a random
distribution.  During this phase, the number is secret.
However, each player publicly commits to the number, using
some agreed-upon cryptologic commitment scheme.  Phase 1
ends when all the commitments have been received by all of
the players.

During phase 2, all the strings are revealed.  Each of the
players can attest that he received all of the commitments
before revealing his string, so again you don't need to
trust every player, so you as you trust at least one.  The 
final answer is the XOR of all the contributed strings.
Anybody on earth can verify the commitments and verify the 
correctness of the XOR computation ... ὅπερ ἔδει δεῖξαι.

This is just a sketch; you can add various bells and whistles
if you like.


By way of contrast, using digits from some mathematical 
constant is not entirely safe, because there are a lot of 
mathematical constants, and each one has a lot of digits,
so a wise guy can just search through them to find something
with the desired backdoor property.

More information about the cryptography mailing list