Re: [Eligibility-discuss] On 3797 alternatives

[Martin Thomson <[e-mail]>]

On Thu, Jun 1, 2023, at 05:54, Eric Rescorla wrote:
>> Given the common practice of choosing several large-scale lottery systems this seems infeasible to me. YMMV of course.
>
> This also matches my intuition, though I don't have any analysis to support it.

Let's take Mega Millions (https://en.wikipedia.org/wiki/Mega_Millions).  Assuming that balls are chosen with close to uniform distribution - a reasonable assumption in this case, I hope -  the amount of entropy in a draw is just over 28 bits.  Enumerating a space of that size is costly, but feasible if you assume that the computations involved are relatively lightweight.

So we might dispense with the notion that some influence on NomCom results is conditional on being able to predict a single lottery, even if predicting the lottery outcome would clearly provide someone more direct and tangible value.  It is more about being able to bias the outcome.

Given knowledge of all possible outcomes, the attacker only has to pick the most favourable outcome of those available to them.  Their computation cost increases basically in proportion to the number of volunteers they control (for Paul's approach, anyway; for 3797 it's a tiny bit more complex, effort might depend on the total pool size).  That is, the attacker is able to choose from the most favourable subset of 2^v options out of a total space of 2^{e+v}, using computation proportional to v.2^e.

To give you an idea of the bounds on potential volunteer control, I found one company domain name in the emails of 188 eligible volunteers; another company appeared 148 times.  The actual number of people who currently work at those companies is likely fewer, but I also didn't consider subsidiaries.  That's a lot of potential control.

It's hard to know whether knowledge of possible outcomes would be enough to justify an attack like this over just stuffing the NomCom with as many people as possible.

Computational bounds are easier to reason about.  If the attacker cannot enumerate a good proportion of the 2^{e+v} space, then they don't guarantee that the bias they introduce is in their favour.

The entropy in a single lottery tends to be fairly small relative to a reasonable computation target - Mega Millions is more than 5 bits stronger than Tatts Lotto, as used last year - but most lotteries will have in the order of million to one prize to ticket ratios, so they will probably want in excess of 20 bits to ensure that they retain the appeal of a big return.  So I'd say that 3 lotteries would be adequate for our purposes.  > 2^60 work is more than we'd allow for something that matters more than this.

On other entropy sources: Picking stocks is highly unlikely to provide the same advantage as a lottery.  A stock or index rarely has a big range.  The Dow Jones has a 6k range over the past year and is usually down to two decimal places.  That's 19 bits at best, but the values are far from uniform, especially over a shorter period (S&P over the past month was 14 bits at best).  The same goes for contests, like horse races, where picking a winner is not the same as choosing uniformly at random, therefore the entropy could be low.  Running an analysis on the basis of the favourite winning is too easy.