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

[Sampo Syreeni]

On 2014-04-01, Miroslav Kratochvil wrote:

> 1. I need N.U.M.S. numbers so that everyone sees I'm not plotting something,
> 2. I need the numbers to match the specification of what the SYND's cipher
> matrices need to look like.

Since I'm not a real cryptographer, take the following with a grain of 
salt. But it does constitute a real protocol for this sort of thing, so 
maybe you or somebody else can derive some benefit from it.

Essentially, you want a trusted source of well behaved bits you can be 
sure of isn't under suspicion. The binary development of pi serves well 
there for at least three separate reason. First, it's a fundamental 
constant with a history of study considerable longer than that of the 
other likely candidate, e. Secondly, it was proven transcendental early 
on, and is conjectured to be normal, with a reasonable chance of one day 
being proven so. And third, spigot algorithms exist to look arbirarily 
far into the development for verification purposes, with a bearable 
complexity profile.

That means you could probably take any thus far unused part of the 
development as your source. But I think it might just pay off to put in 
an extra step which guarantees that not only do you have to use the next 
portion nobody used yet, but to also expend an amount of effort doing 
so. Also, you probably shouldn't be able to choose where you start your 
extraction, at leaast if you get to choose how many bits you're going to 
extract at the same time. And of course the effort should be roughly 
(asymptotically) equal, whether you took two bits separately or a single 
two bit chunk.

Under those constraints the best I can do is to encode the number of 
bits you need using as early as possible a universal code, then starting 
with the last unused bit position seen in the freely available 
literature scan forward till you see the coded representation, and then 
extract the number of following bits represented by that code. The 
Levenstein code was the first universal code, but it suffers from the 
fact that it's a single bit too long for the application at hand because 
it encodes zero as well, doubling the hardness of the search step. Thus 
the best code for this sort of thing is probably the Elias Omega.

A construction like that leaves very little upto doubt as to your 
choice, and it comes with nice enough properties that it could actually 
be of general utility. Of course, what you then do with those bits is 
another matter. Once you have them, you still have quite a lot of leeway 
in how (especially in which order) you assign them to your crypto 
primitive's free variables. So that leeway should be minimized 
separately, too. However that's the kind of problem I can't even begin 
to touch, because really doing it right essentially amounts to 
canonicalizing and ordering the whole class of finite width boolean 
circuits. That is then a very hard problem indeed.
-- 
Sampo Syreeni, aka decoy - decoy at iki.fi, http://decoy.iki.fi/front
+358-40-3255353, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2