Re: discussion of publicly verifiable random selection procedure in internet-drafts that led up to RFC 2777

Subject: nomcom algorithm: the last input to be made public matters most
Date: Wed, 14 Oct 98 00:25:42 IDT
From: Neal McBurnett <nealmcb@lucent.com>
To: poised@tis.com
Reply-to: Neal McBurnett <nealmcb@bell-labs.com>


The selection procedure before us and the draft it is based on seem
most highly focussed on demonstrating that Don did not manage to
cleverly pick an algorithm which allows him to influence the winners
ahead-of-time.  I see no reason to challenge that assertion.

But the more important question, I think, is whether *anyone else* can
improperly influence the selection result.  After all, we are likely
to be picking nomcom chairs who have ethical reputations.  But many
people who are not picked to be part of the process at all may want to
affect the outcome.

Imagine an adversary "Mallet" who simply wants to see that a
particular person is picked for the committee.  In this case, with an
average selection probability of about 1 in 4 (10 out of 41), Mallet
simply needs to move the result into one of 4 equally large result
sets.

All Mallet has to do is observe the various inputs as they are made
public and then influence the *last* source of input.  In this case it
appears that the last source is the Massachusetts Numbers Game draw
time: 19:55 US/Eastern on the 16th.
	<http://www.masslottery.com/>>

If Mallet could manipulate even just the last digit of that number,
he could probably manage to pick one or two members of the
committee.

even if there is ample entropy in the whole set of inputs, if the last
input can be swayed, an adversary can have their way.  Suppose that
instead the stock prices were the last inputs to be publicly
available.  Moving the price of Cybercash stock for one day (volume of
165,200 shares today at a price of 7 1/8) would not be too hard to do.
Little money would be at risk if the original stock position was
brought back to its previous level in the next few days.  Selecting
the closing price to target would be done by estimating the closing
prices of the other stocks as the day ended, and running the algorithm
with those prices and all the other inputs plugged in to see which
Cybercash prices would result in the best algorithm outcome.

[What are the criteria for making information on individual stock
trades public?  How much shows up on the ticker tapes?
Who will be watching Cybercash on Friday?  :-]

Even if Mallet can't affect the last input, it may be possible
to influence other inputs in such a way that the overall outcome
is biased.

I suggest that it would be preferable to select several inputs that
all are announced at the same time by different jurisdictions.
Stocks, stock trading volumes, and even stock indexes are probably a
poor choice as inputs from this standpoint.  Lotteries seem useful in
this context, and it is nice to be able to use the lottery
infrastructure for something more enlightened than their raison d'
etre.

Cheers,

Neal McBurnett <nealmcb@bell-labs.com>>  303-538-4852 Denver
Bell Labs / Lucent Technologies
http://bcn.boulder.co.us/~neal/      (with PGP key)