[messaging] collaborative random number generation

[Thomas Baigneres]

Hi Joseph,

while searching for a proper way to generate parameters for a new elliptic curve, we (CryptoExperts) came up with another alternative based on national lotteries. Nothing really new here, but we propose a way to combine draws from different lotteries in a way that makes manipulation hard. We are currently looking for feedback on this article.

paper: https://eprint.iacr.org/2015/1249
project website: http://cryptoexperts.github.io/million-dollar-curve/
source code: https://github.com/CryptoExperts/million-dollar-curve

Sorry for promoting my own work ;-)

Regards

Thomas


> On 11 Dec 2015, at 01:15, Joseph Bonneau <jbonneau at cs.stanford.edu> wrote:
> 
> I can give some context on public randomness sources since I have been thinking about this a lot over the past year. This is tangentially related to secure messaging but here is a summary.
> 
> There are 3 basic approaches I know of:
> (1) Commit and reveal. This either requires bounties to punish participants who don't reveal (this can be enforced in Bitcoin or similar cryptocurrencies) or the protocol is vulnerable to manipulation by parties who don't reveal.
> 
> (2) The unicorn protocol proposed by Lenstra/Wesolowski (https://eprint.iacr.org/2015/366.pdf). Any party can submit random nonces directly and the result is a hash of all of them. But, the hash is a specially designed slow and non-parallelisable hash. At time t0 you stop accepting new inputs, and the hash takes until time t1 to complete. (t1-t0) must be long enough that it is beyond any reasonable clock skew. This is a promising approach but has a few problems in practice, you have to reason about clock skew and hardware acceleration of the hash and it requires a designated leader.
> 
> (3) Randomness as a byproduct of Bitcoin-style consensus protocols. I wrote this up here: https://eprint.iacr.org/2015/1015.pdf. The basic idea is that you hash the most recent Bitcoin block. The puzzle solution guarantees that there is significant min-entropy in each block, equal to the difficulty of the puzzle. Manipulating this requires manipulating the consensus protocol, either by finding valid blocks and discarding them or trying to preferentially propagate blocks in the event of a tie. These attacks are clearly computationally possible, but expensive. Bitcoin is designed to make them hard.
> 
> Personally I lean towards approach #3 being the most practical for many applications, including yours. If the adversary's goal is to violate privacy and they have to launch an expensive attack on Bitcoin consensus to do it, you are probably okay. The nice part is that the protocol is completely non-interactive, everybody just samples from the Bitcoin network and you have your randomness.
> 
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging