|
|
|
|
|
Distributed Surveillance Project |
Keywords: random selection, randomized protocol, randomized multiparty computation, multiparty computation, randomness
Citation:
Abstract
Consider a set of players who wish to randomly arrange themselves without a trusted third-party. For example, if there are 3 players, a, b and c, then a trusted third party could order them as abc, acb, bac, bca, cab, or cba. In the absence of a trusted third party, the players want to select one of these permutations for themselves at random. In this writing, a protocol (named “RandomSelect”) is presented using multiplayer computation. From a bag of all possible ways the players could be ordered, RandomSelect provides a means for players to make local choices that when combined, jointly select a permutation randomly. The RandomSelect protocol supports any number (n) of two or more players and computes properly even if n-1 players collude. Communication is O(n) using a broadcast channel. More generally, necessary and sufficient conditions for a class of functions called “RandomOrder” functions are defined. A RandomOrder function uses n inputs to make a random selection of a string from a bag of n! strings where all possible selections are uniformly distributed over the possible inputs and over the strings. Any RandomOrder function can be used in the RandomSelect protocol. Bio-terrorism surveillance is used as an example application.
L. Sweeney and M. Shamos
A Multiparty Computation for Randomly Ordering Players and Making Random
Selections. Carnegie Mellon University, School of Computer Science, Technical Report, CMU-ISRI-04-126. Pittsburgh: July 2004.
(PDF).
Related Links