Re: [Eligibility-discuss] On 3797 alternatives

[Donald Eastlake <[e-mail]>]

Hi Martin,

I'm fine with assuming a single attacker but I am concerned about over
complicating things to, say, block the attacker from inducing a bias of say
1 part in a million.

Below are some numbers which, while not directly applicable to the attack
you are talking about, are, I think, indicative of the miniscule biases we
may be talking about.

It depends a bit but I think that when you make many selections of n items
from a population p with replacement (which is approximately true if p>>n)
and do this t times, obviously the expected number of times a particular
item would be chosen is t*(n/p). Making some simplifying assumptions, the
standard deviation of the number of times a particular item would be chosen
is, I think, SQRT(t*(n/p)*(1-(n/p))). Assume you are selecting 10 items
from 200, about what the current nomcom selection is. Using those
equations, with an abysmal 10 bits of entropy, that is selection 10 at
random from 200 and doing it randomly just 1024 times, the expected number
of times an entry would be selection is 51.2 and the standard deviation of
the number of times it is selected is 6.97 or 13.6% of the expected value,
which I would consider unacceptable. Move up to 20 bits, that is selecting
randomly 2**20 or 1,048,576 times, and the expected number of times an item
is selected is 52,429 but the standard deviation in the number of times it
is selected is only 223 or 0.426% of the expected value which I would
consider marginal at best. With 30 bits, this is selecting randomly 2**30
times, the expected number of times selected is 53,687,091 with a standard
deviation of 7,142 or just 0.013% of the expected value, which I consider
acceptable. But RFC 3797 and rfc3793bis recommend a minimum of 40 bits of
entropy which implies about 2**40 or 1.1E12 selections so the expected
times an item is selected is 5.5E10 with a standard deviation of 228,532 or
just 0.00042% of the expected value. So, even though it takes a minimum of
54 bits of entropy to do completely random selection of 10 items from 200,
with just 40 bits of entropy, under the assumptions above, the probability
of a particular item being selected will deviate from perfect randomness
only by an insignificant amount, as asserted in RFC 3797 and rfc3797bis.

So, what is a reasonable estimate of the amount of bias that can be
introduced by the attack you hypothesize?

Thanks,
Donald
===============================
 Donald E. Eastlake 3rd   [phone] (cell)
 2386 Panoramic Circle, Apopka, FL 32703 USA
 [e-mail]


On Thu, Jun 1, 2023 at 10:01 PM Martin Thomson <[e-mail]> wrote:

> 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.
>
>
>