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

Viktor Dukhovni cryptography at dukhovni.org
Sun Mar 30 16:41:12 EDT 2014

On Sun, Mar 30, 2014 at 08:43:14PM +0200, Miroslav Kratochvil wrote:

> The problem is that I need a very big amount of provably random constants
> for initialization of the content of some internal matrices (A_1 and A_2 in
> the paper; only thing that the authors specify about them is that the bits
> need to be uniformly random, not secret).

Point of terminology: the above as stated is essentially nonsense.
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.  The security of
any PRNG keystream generated from a seed with n-bits of entropy is
never stronger than n-bits.

Therefore, either:

    - a constant is just fine, and what you're looking for is not
      "random", but rather "unlikely to be backdoored in some
      non-obvious way".


    - constant is not fine, and you need randomly chosen data with
      sufficiently high entropy.

For the former, given the large number of bits to generate, you
could indeed go with go with digits of sqrt(2), e, or pi, whichever
is more convenient (to store or even generate at run-time).

For the latter, your provable keystream generator is only as secure
as its initialization.

> I will certainly not use exactly these NUMS to fill up the syndrome
> matrices, I instead want to feed them to "preparation" phase that will run
> XSYND with NUMS and supplied key+IV several times to generate the contents
> of new A_i matrices that will be used to generate the actual keystream.
> Or should I use some simpler key expansion function, even when XSYND is
> there already a key expansion function?
> Or did I get it completely wrong?

I would contact the authors and see what they have to say about how to
prepare the "known" "random matrix".  While apparently, unlike the key,
the "random" matrix need not be kept secret, it is not clear whether it
can be simply constant, or needs to be "random" is some stronger sense.


More information about the cryptography mailing list