ABSTRACT
Suppose we are given n buckets with varying integral sizes, and wish to fill some fraction alpha of them with balls, with a bucket of size k being filled as soon as it receives k balls. Our goal is to minimize the number of balls used.
If we know the sizes of the buckets, this is a trivial problem: Just identify the (alpha)n smallest buckets, and fill them. But what if we do not know the sizes of the buckets in advance, and after each ball placement only find out whether the bucket is now full or not?
This problem models a cryptographic question. Suppose an adversary wishes to prevent a multiparty protocol from succeeding. Typically with such protocols, the adversary need only corrupt half (or a third) of the parties to attain its goal. But suppose each party is protected by a sequence of some number of cryptographic walls, each of which requires a certain amount of computation to break through. If parties have differing numbers of walls, and the adversary does not know how many walls a given party has until it breaks through the last one, we get our balls-and-buckets problem.
This cryptographic connection is formalized in a paper I've written with Juan Garay, Aggelos Kiayis, and Moti Yung. Here I will concentrate on the combinatorial side, giving algorithms for the adversary (bucket filler) in the presence various levels of partial information about the sizes, and near-matching lower bounds on what is possible, both for deterministic and randomized algorithms. I also address the question of how a system-designer can best spend his security dollars (in wall building) in the hidden diversity setting.
