A search for better methods is being coordinated by The Bridge World Magazine. I think the problem may interest some of IACR's members, so I'd like to act as a "synapse" between the two communities. Jeff Rubens has given us permission to reprint his recent editorial, which is attached below. It includes an email address (dealing@bridgeworld.com) for getting included in their discussions.
Matt Franklin
Reprinted from The Bridge World Magazine, Editorial, May 1999:
We propose, will help to organize, and will act as a clearinghouse for a worldwide effort to produce a standard deal-generating procedure. If implemented with care, checked thoroughly, and adopted everywhere, such a method would have many significant advantages over the current approach, including:
(1) Avoiding the unrecoverable disaster of players' recognizing the reappearance of an old set of deals.
(2) Facilitating the distribution of information. Organizers of multi-site events using duplicated boards could distribute the information needed to create the deals cheaply and quickly, reducing expenses and minimizing some security problems.
(3) Producing instantaneity. Enthusiasts everywhere could play the deals from a major event, such as a world or national championship, soon after (or even, with appropriate security at the tournament site, simultaneously with) the participants, then compare their results with the stars'. This capability could open a new avenue for increasing the popularity of bridge.
(4) Keystroking reduction. Less typing would be needed for the publication of deals on the Internet and in books that record the proceedings of major events.
(5) Eliminating accusations of rigging. Sponsors of events featuring duplicated boards at multiple sites are sometimes accused of editing the deal sets, perhaps of "giving ample opportunities to both North-South and East-West." Such manipulating, which changes the nature of the game, is the organizational equivalent of prearranged secret signals between partners; both behaviors should engender severe, permanent penalties. It is extremely difficult either to sustain or to defend such a charge. A good way to handle the situation is to make fixing as close to impossible as we can, eliminating both the act and the charges.
To stimulate thought about and action on the problem, we've put some preliminary discussion and a sample outline into a sidebar (see "A Three-Minute Algorithm"). If you want to participate in the creation, evaluation and testing of a standard dealing algorithm and programs that implement it, send an e-mail to dealing@bridgeworld.com that includes in its body your name, postal address, and e-mail address. After allowing time for signups, we will send the list of e-mail addresses to all participants, anticipate discussion and sharing of ideas among interested parties, and keep track of any results that arrive later at the "dealing" e-mail address.
1. Highest importance: Capability of convincing the public both that the dealing is mathematically correct and that everything is on the up-and-up.
2. High importance: Simple involvement in each job of a very long "seed" number that avoids reruns.
3. Fairly high importance: Ease of understanding and use, hence accessibility to "home" programmers with only moderate effort.
4. Medium importance: High difficulty of cryptanalysis from observed partial output.
5. Low importance: Machine efficiency. (Any reasonable program is going to run much faster than needed and take up less space than available, even on somewhat outdated personal computers.)
Having done that, the next time we were stuck waiting for an egg-timer to trigger our further activities, we considered what algorithm might meet the criteria. Here is what we produced before the egg was ready to eat:
(a) Establish a bank of a moderate number (six, say) of easy-to-program pseudorandom number generators (linear congruential, perhaps).
(b) When ready to generate a set of deals, create a long seed number whose inputs are the date, the standard time at a fixed location (Greenwich, England?), the international calling code for the home country of creation, and many digits from each of at least three people (of whom at least one is local and at least one is not, the latter presumably communicating by telephone or by e-mail--a distant contributor may send digits unencrypted and need verify only that the set was created immediately after his portion was sent, making prearrangement impossible without his participation).
(c) Use subsets of the seed's digits to initialize the number generators. Whenever a pseudorandom value is needed, use output from the first generator to create an integer that points at one of the others, then use the indicated generator to create a value in the interval from zero to less than one.
(d) Use a number derived from (c) to determine how many of the deals first produced (or how many pseudorandom numbers) to discard. Then, for each deal, use 39 outputs from (c) to distribute one of the remaining cards to the appropriate players, by thinking of the unit interval first as broken into fifty-seconds, then into fifty-firsts, etc.
We anticipate that a collective effort based on longer periods of thought (perhaps by programmers who prefer their eggs hard-boiled), whether using our general approach or not, will produce a satisfactory universal standard.