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

[Natanael]

Den 2 apr 2014 04:08 skrev "Sampo Syreeni" <decoy at iki.fi>:
>
> On 2014-04-01, Albert Lunde wrote:
>
>> In this kind of construction, the "something up my sleeve" may appear to
be how you picked the starting point and other details.
>
>
> That is why I put in Elias's omega code, because to my knowledge it's the
first optimal construction of a universal code Levenstein's, and it always
starts from one, so that you can't repeatedly extract zero bits and by that
way get around the idea that you shouldn't be able to precisely choose
where you start your extraction.
>
> Second, since the set of extant cryptographers is disributed and
ostensibly a novel algorithm needing low-sleeveness numbers might even come
from outside the known mainstream, I can't think of any lower complexity
protocol which just lets you extract arbitrary amounts of nice bits from a
commonly trusted source, than this one, combined with some kind of
plausible enough notarization to establish precedence in case of dispute
over who owns the currently-considered-to-be-spent-bits.

[...]

Here's my take on it (might be unnecessarily complicated);

You use one of those Pi digits calculation methods in an algorithm that
decides the depth into the decimals of Pi to calculate the numbers at from
the input number. This can intentionally be computationally heavy á la
scrypt and bcrypt. So given a unique input with a source that is verifiably
hard to influence you have a (most likely) unique output that is very hard
to influence and no mathematical structure you can influence.

Now, how to calculate the input to it:

You can use a commitment hash of a random value that you publish in the
Bitcoin blockchain together with a number that specifies which future
block's hash to use. This can be a fixed number, like 12 (with a block time
of 10min that's 2h in the future on average). The commitment can both
include a random number and reference the context it is used in (hash of
session key, or time + name of your project) to prevent undetectable reuse
and guarantee uniqueness for each purpose.

When that block is reached, you combine the committed value (including it's
referenced context to prevent reuse), the block hash and the public key
that was used for the commitment transaction. The combination method can be
a hash of all inputs or XOR.

That means the chosen depth is different for every user, is different for
every use, is verifiable and extremely difficult to influence.

Influencing the block hash (in competition with plenty of miners with
SHA256 ASICs) + your committed value + your public key to result in a weak
output by the Pi decimals calculation would require computational power
that by far exceeds the entire Bitcoin mining network many times over -
which itself outperforms the entire top 100 (public) supercomputers
together (on hash calculations)!

You can also directly detect in the blockchain if somebody attempts to
reuse the same input values for something else.

The depth into the Pi decimals is also very likely to be unique, and thus
to provide a unique output. (There's your coordination to not reuse
numbers, the blockchain is global, and also works perfectly fine as a
notary.)

In case the numbers in Pi would be shown to have an exploitable structure
for your use case, you can switch constant. In case it would still be
unique enough and you have a trusted hash function, you can simply just use
that hash on the output.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140402/2e9926c2/attachment.html>