# Estimating a percentile among distributed nodes without revealing values

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.

• 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. – cardinal Apr 1 '11 at 13:34
• 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. – whuber Apr 10 '11 at 17:14
• 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? – Jukka Suomela Apr 10 '11 at 17:55
• Have you considered Yao's Millionaires' Problem? It allows secure comparison with much less computation. – M.S. Dousti Apr 11 '11 at 17:53
• 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$. – Massimo Cafaro Feb 8 '12 at 17:20