[curves] Million Dollar Curve

[Gregory Maxwell]

On Thu, Feb 25, 2016 at 1:08 AM, D. J. Bernstein <djb at cr.yp.to> wrote:
>> “provably” random parameters
>
> Consider the October 2015 conviction of an insider who successfully
> compromised the security of a typical modern lottery "by using his
> privileged access to an MUSL facility to install a rootkit on the
> computer containing Hot Lotto's random number generator":

Beat me to the link. There are, IMO, better schemes for NUMs.

My "favorite"* is a scheme where:

(1) Rigidly define the use of the resulting randomness and agree on
it, in some document with known hash. (Ideally, you provide a program
that writes the implementations and papers on the resulting
cryptosystem given a seed)

(2) Pay bitcoin to N respected parties who have randomly generated
their own keys (idenfied in (1)).

(3) Perform a transaction committing to the scheme hash.

(4) Once that settles in the Bitcoin network, the N parties sweep
their coins and publish their private keys.

NUMS initialization is a random hash (specified in (1)) of the block
data where settlement happened in (4), along with the private keys.

Grinding the NUMS requires 2^70 SHA2 executions per try on average,
knowledge of all N of the secrets, and a grinder needs to win the
block race.  Any party who knows any of the N secrets could also steal
the coins on deposit instead of trying to grind; incentivizing the
respected parties to choose unpredictable secrets and keep them
secret.

I believe the primary vectors for biasing the outcomes are in the
construction of the usage in step (1), and the potential for
participants to bias the outcome by 'losing' their private keys if it
doesn't go their way. The latter could be discouraged by the loss of
funds (esp if the release requires signatures by all parties), which
could be quite large... but perhaps still not high enough to thwart
nation-state attackers.

The primary argument for this scheme is that you can argue its
security under several distinct angles: The personal integrity of any
one of the N secret holders, the computational challenge of the
hashcash inner-loop, the bonding to encourage secrecy, or the
competition of the Bitcoin block race.

*"favorite" in the sense that I think NUMS schemes should be avoided
at all cost; if for no other reason than they invite precisely this
sort of endless shed painting!