(The following is based on some recent joint work of myself, Dov Gordon, and Vinod Vaikuntanathan.)
Consider the following coin-weighing problem.
You are given coins, all-but-one of which weigh the same amount (say, 1 unit each). Call the outlier a “bad” coin. You have access to a scale that supports the following operation: you can place any number of coins on it, and ask whether the total weight of the coins on the scale is equal to some value. Since you know nothing about the weight of the bad coin, this is equivalent to asking whether some subset of the coins contains the bad coin or not.
How do you determine the bad coin in the fewest number of weighings? I’ll let you think about it for 1 paragraph; the solution is given below.
I am sure I have seen this question before, possibly in a list of interview questions. But when the question recently came up in the context of something I was working on, I couldn’t find any reference to this problem. If anyone is aware of one, please let me know.
Here is a solution using weighings, which is easily shown to be optimal. Number the coins (in binary) from to and define subsets , where contains all coins whose th bit is ‘1’. If we assign a ‘1’ to the indices of those subsets that weigh the wrong amount, we exactly recover the binary representation of the bad coin.
What about the general case, where there are up to bad coins? Generalizing the above, what we want is to associate each coin with a subset , indicating that coin is placed in sets (and then the sets are weighed as above). If we want this process to uniquely identify any set of or fewer bad coins, then the property we need is that the are –union free: basically, this means that the union of any two distinct collections of or fewer of the yield distinct subsets of . What is the dependence of on ? (A lower bound of is immediate.)
It turns out that this notion is tightly connected to a more familiar one, cover free families (a google search will turn up a definition). We showed:
Any -cover free family is also -union free. Conversely, any -union free family is also -cover free.
Cover-free families are well studied. Optimal (explicit) constructions are not known, but a result of Kumar, Rajagopalan and Sahai shows that is achievable.
What is the cryptographic connection? I’m simplifying a bit here, but imagine we want to perform batch verification of signatures where up to might be invalid. How quickly can we identify the bad ones, if we assume as an atomic primitive a way to identify whether any collection of signatures contains all valid signatures? (Obviously, this is only of interest if the cost is less than verifications of individual signatures. Schemes with this property are known.) The above approach gives a solution where only “batch verifications” are needed. (I want to point out that better solutions are known when the batch verifications performed (i.e., the sets ) can be chosen adaptively. In our case, we explicitly wanted a non-adaptive solution where the batch verifications could be parallelized. For further details, you will have to wait for the eventual paper.)
All-in-all, a fun problem with some neat connections to combinatorics.