Posted by: jonkatz | July 24, 2009

A coin-weighing problem (and a cryptographic application)

(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 n 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 S 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 k=O(\log n) weighings, which is easily shown to be optimal. Number the coins (in binary) from 1 to n and define subsets S_1, \ldots, S_k, where S_i contains all coins whose ith 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 t bad coins? Generalizing the above, what we want is to associate each coin i with a subset T_i \subseteq \{1, \ldots, k\}, indicating that coin i is placed in sets \{S_j\}_{j \in T_i} (and then the sets are weighed as above). If we want this process to uniquely identify any set of t or fewer bad coins, then the property we need is that the \{T_i\} are tunion free: basically, this means that the union of any two distinct collections of t or fewer of the \{T_i\} yield distinct subsets of \{1, \ldots, k\}. What is the dependence of k on n, t? (A lower bound of k \geq \log {n \choose t} = O(t \log n) 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:

Lemma:
Any t-cover free family is also t-union free. Conversely, any t-union free family is also (t-1)-cover free.

Cover-free families are well studied. Optimal (explicit) constructions are not known, but a result of Kumar, Rajagopalan and Sahai shows that k = O(t^2 \log^2 n) is achievable.

What is the cryptographic connection? I’m simplifying a bit here, but imagine we want to perform batch verification of n signatures where up to t 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 \ell signatures contains all valid signatures? (Obviously, this is only of interest if the cost is less than \ell verifications of individual signatures. Schemes with this property are known.) The above approach gives a solution where only k “batch verifications” are needed. (I want to point out that better solutions are known when the batch verifications performed (i.e., the sets \{T_i\}) 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.

Advertisements

Responses

  1. Dear Jonathan,

    The subject you should look into is Combinatorial Group Testing. The monograph by Ding-Zhu Du and Frank Hwang is authoritative.

    t-cover-free families are equivalent to something called t-disjunct matrices (just the matrix whose columns are characteristic vectors of the sets in the family)

    t-union-free families are equivalent to something called t-separable matrices.

    The lemma you stated is well-known (see the textbook).

    There are many known constructions showing that k = O(t^2\log n) is possible, including a construction given in the following paper

    Ely Porat, Amir Rothschild: Explicit Non-adaptive Combinatorial Group Testing Schemes. ICALP (1) 2008: 748-759

    THere’s also a recent submission showing that we can attain k = O(t^2\log n) AND efficiently “decode” the bad coins given the weighing outcomes. (Please email me for details if you’re interested.)

    If you want a super-quick reference to non-adaptive combinatorial group testing, this (old) survey probably helps:

    http://www.cse.buffalo.edu/~hungngo/papers/dimacsCGT.pdf

    Regards,
    Hung

  2. Just a typo:

    In the para above the Lemma, k > log(n\choose t) = O(t logn)

  3. Hung, thanks very much for the pointers!

  4. In the second half of your problem (when there is more than one bad coin):

    What happens if one bad coin weighs 1.5 units and the other weighs 0.5 units? Can you tell them apart from two good coins if they’re weighed together?

  5. Ranjit – thanks, I corrected it.

    Kevin – Sorry I didn’t make it clear. The assumption is that the weights of the bad coins do not “cancel out”. (If you want, you can imagine they are all light or all heavy.) For the particular application to signatures, one has to prove that multiple “bad” signatures can never combine to give a positive batch verification.

  6. Also a reference: http://www.jstor.org/pss/2975353

  7. Helger – thanks for the link.

    I should make clear that I was able to find lots of references for the version of the problem where the scale indicates whether the pile of coins being weighed is heavy, light, or the correct weight. But in the variant of the problem discussed in the post, the scale only tells you whether the weight is correct or not.

  8. You may also look at
    http://eprint.iacr.org/2009/240


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: