[Cryptography] Secure random mixing

Phillip Hallam-Baker hallam at gmail.com
Tue Nov 12 15:18:58 EST 2013


Along the way someone suggested

R1(t) | R2(t) | R3(t)

As a randomness function that prevents bias. But actually it does not since
it allows any of the parties to control the output provided that they are
the last to vote. This is a better approach:

H(R1(t) + R2(t) + R3(t))


There is always going to be a byzantine generals issue here. What you need
to avoid that is to have the parties commit to a value before the other
parties reveal their value.

So a better protocol would be to construct the beacon as a Lamport hash
chain and reveal the previous value on each tick. We can now eliminate the
possibility of collusion as the beacon is committed to its value before the
other parties.

The only way to cause a default is if there is a three way collusion and
the beacon provider reveals the source value in advance.


This does sound to me like a function that NIST and its equivalents in
other countries could usefully provide. It would be a 'starter function'
for a state cryptographic bureau (along with a signed time function).

I would imagine the following functions to be potentially useful:

1) A year chain with a time increment of minutes
2) A ten year chain with a time increment of hours
3) A hundred year chain with a time increment of days

A new chain would be started each month for 1, each year for 2 and each
decade for 3 so that there is overlap.

This is a pretty modest outlay. The biggest CP commitment is for chain 1
which is only half a million operations.

The providers could sign all the overlapping chains at the same time as
there are at most 32*8 bytes of chain data.

(Thinking about my trust model, chain 2 is probably redundant)


Governments could have fun promoting their domestic provider of trusted
chain.

And I am sure someone has thought of this before, possibly Lamport himself.


-- 
Website: http://hallambaker.com/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131112/6edf7f26/attachment.html>


More information about the cryptography mailing list