[Cryptography] ideas for (long) Nothing up my sleeve numbers
Sampo Syreeni
decoy at iki.fi
Tue Apr 1 18:27:48 EDT 2014
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
More information about the cryptography
mailing list