Randomness is a lottery, so why not use a lottery for randomness?

A group of French cryptographers reckons public lotteries are the perfect seed for elliptic curve cryptography.

The group from company CryptoExperts and boffins from the Laboratoire de Mathematiques de Versailles in the University of Paris-Saclay playfully calls the scheme the “Million Dollar Curve” (modest in a world where the record as-yet-unclaimed jackpot is more than a billion dollars).

They note that they “we propose a hopefully convincing (and amusing) solution to the problem of generating publicly verifiable randomness in an unimpeachable fashion”.

The problem they're working on is that all elliptic curves have to be seeded somehow, and experience teaches us that seeding mechanisms can be dangerously opaque and esoteric. That, after all, is how the NSA's DUAL EC DRBG was able to survive so long as a random bit generator before it was found to be rubbish.

In the Million Dollar Curve model, explained in this paper, the boffins write that public lotteries have two attractive characteristics as seeds: they're easy to verify (since everybody knows the results), but hard to manipulate.

“Our method allows to build what we call a Publicly verifiable RNG, from which we extract a seed that is used to instantiate and initialise a BlumBlum-Shub random generator. We then use the binary stream produced by this generator as an input to a filtering function which deterministically outputs secure and uniformly distributed parameters from uniform bitstreams”.

While other possible sources of verifiable randomness are feasible, they write, they often rely on a trusted third party somewhere in the chain – something not required if the source of the seed is public knowledge, like the winning numbers of a lottery.

The lottery numbers are also archived, and that means cryptographers of the future can easily go back over the outputs of the scheme and verify the outputs of the crypto-scheme.

They note that Bitcoin's blockchain is, similarly, a source of publicly-verifiable and archivable data that's hard to predict in advance, but that was someone else's academic paper.

The group has set up a GitHub site for the Million Dollar Curve here. ®