23
$\begingroup$

I have a fairly unique problem to solve and I am hoping somebody here can give me some insight into how to best tackle it.

Problem: Suppose a list of N numbers is shared among a set of participants in such a way that no single participant actually knows any of the numbers they share. All participants know N (the size of the list of numbers) and the sum of all of the numbers on the list, but nothing more a priori.

By working together, it is possible to compare two shared numbers a and b in such a way that the participants learn whether the statement "a < b" is true, but nothing more. However, this is an extremely expensive thing to do (read: it could take many seconds, perhaps even minutes, to complete a single comparison). See the end of this post for a bit more information on how such a thing is possible.

At the end of the day, the parties wish to output of which indices in the list correspond to the "top K percent" (the K% which is largest) shared numbers in the list. This can of course be done by sorting, or using a "top K" selection algorithm. However, these tend to use an aweful lot of comparisons, which is to be avoided. (These are either O(n log n) or O(n), with fairly large hidden constants.)

Another alternative is to "guess" at a number X for which (1-K)% are smaller than X and K% are larger. Then you can compare each element with X and see how many are larger and how many are smaller. If your guess was wrong, revise it using something like a binary search until you converge on a correct solution. This takes far fewer comparisons if your guess is good.

So, my question is,

Given only N and the sum, what is the best way to "predict" X?

Of course this will depend on the underlying distribution. For different use-cases the underlying distribution will likely be different but will be known, so I am interested in good solutions for all the common ones (normal, uniform, exponential, perhaps a few others). I would also love to hear suggestions regarding how best to do the "binary-like" search to minimize the number of steps given an assumption about the underlying distribution.

APPENDIX: Each value on the list is shared among participants using Shamir's secret sharing scheme. Suppose there are M participants and the list is of length N. Then, the i-th number on the list is represented by a polynomial $f_i$ of degree M-1 over some finite field F. The constant term of $f_i$ is the number that is shared, all other coefficients are chosen uniformly at random from F. The j-th participant's shares are then $f_i(j)$, $1\leq i\leq N$. Given this share, the participant has no information (in an information-theoretic sense) about the number; in fact, no proper subset of participants can combine knowledge to learn any information about the shared numbers. However, using a sophisticated secure multi-party computation technique, it is possible to determine if one shared value is less than another without revealing any more information. This technique involves all participants cooperating, which is why it is so costly to do and should be done the fewest number of times possible.

Improve this question
$\endgroup$
12
  • $\begingroup$ This sounds interesting, but I don't fully understand the process yet. Can you clarify, particularly the second paragraph? How many participants $M$? Is $M$ greater than, less than, or equal to $N$? Does each participant know some subset of the numbers? Obviously they can't all just know $N$ and the sum since then there is no way to ask any question or collaborate in a way that aggregates information about $a < b$. Are there restrictions on the kinds of questions that can be asked? I look forward to your edit. $\endgroup$
    – cardinal
    Commented Apr 1, 2011 at 13:34
  • 1
    $\begingroup$ Because this question appears to be more algorithmic than statistical (a request for clarification in this regard got no response) and the statistics community has not offered a viable reply, let's migrate to TCS to see whether it generates any interest there. $\endgroup$
    – whuber
    Commented Apr 10, 2011 at 17:14
  • 6
    $\begingroup$ The real question seems to be simply the following: "If we know the distribution, how can we exploit this information in the design of a comparison-based selection algorithm? The algorithm should use as few comparisons as possible (in expectation; the constant factors matter)." Did I get this right? $\endgroup$
    – Jukka Suomela
    Commented Apr 10, 2011 at 17:55
  • 2
    $\begingroup$ Have you considered Yao's Millionaires' Problem? It allows secure comparison with much less computation. $\endgroup$
    – Sadeq Dousti
    Commented Apr 11, 2011 at 17:53
  • 3
    $\begingroup$ Please note that your assumption "in fact, no proper subset of participants can combine knowledge to learn any information about the shared numbers" is false. Indeed, the Shamir's secret sharing scheme is actually a $(k, n)$ threshold scheme in which you distributes $n$ shares of your secret so that at least $k$ shares can successfully reconstruct the secret (using interpolation). Even in the case of a $(n, n)$ scheme all of the participants together are able to reconstruct the secret. Of course, you usually use this scheme with $k << n$. $\endgroup$
    – Massimo Cafaro
    Commented Feb 8, 2012 at 17:20

1 Answer 1

Reset to default
1
$\begingroup$

You seem to ask two related questions:

  1. “which indices in the list correspond to the top”
  2. “Estimating a percentile”, “a number X for which … K% are larger”

These may need very different numbers of pairwise comparisons.

An other aspect that may have significant impact is what information is shared. Everybody knows the number he received, knows the sum, and the yes/no results of comparisons they have taken part in. However, you also say that “parties wish to output of which indices in the list correspond to the top” thus you suggest that some information about the indices will be shared. Depending on what exactly is shared you may get very different solutions again.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Sorry, I must not have been sufficiently clear. Nobody knows a single number on the list; instead, they each have a list of N "shares of numbers" (using Shamir's Secret Sharing scheme, if you aren't familiar with the concepts of shares of a number). So, the only a priori information that any single participant has is N and the sum of all numbers in the list. They each have a bit of information about each number, but not enough information to know what that number is. $\endgroup$
    – ryan
    Commented Apr 1, 2011 at 13:48
  • $\begingroup$ As far as the two related questions go, the second question implies an efficient solution to the first. If I can find X using few comparisons (which I can do if I can come up with a reasonably good initial guess), then I find the indices of all values larger than X using just N more comparisons (these comparisons are also cheaper, since knowing X instead of having a share of X cuts the cost of a comparison down by about 1 third.) General purpose algorithms for finding the top K will typically use far more comparisons for large list sizes, assuming I can find X using ~log(X) comparisons $\endgroup$
    – ryan
    Commented Apr 1, 2011 at 13:52
  • $\begingroup$ Thanks for the comment answers and the appendix to the original question. Now the problem looks different. $\endgroup$
    – GaBorgulya
    Commented Apr 1, 2011 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.