how to get top 10 numbers after using Pallier cryptosystem Assume I encrypted 1000 Integers using the pallier cryptosystem.

Since each time I encrypt a number using pallier I'm using a random r element from Z* then the encrypted numbers aren't in order anymore i,e: we have 2&lt;3 but Enc(2) with pallier doesn't necessarily mean it is &lt; then Enc(3) with pallier.

So how would it be possible to get the top 10 biggest Integers out of those 1000 Integers  when the numbers are encrypted?
So how would it be possible to get the top 10 biggest Integers out of those 1000 Integers  when the numbers are encrypted?


That's easy; decrypt them with the private key, and then pick out the top 10 plaintexts...

If you don't have the private key (and can't interact with someone who does have the private key), then we hope it's impossible.  I say 'hope', because if it were possible, then you could deduce the contents of a Paillier ciphertext with just the public key (and hence, Paillier would be insecure).

Suppose we did have a way to find the top 10 out of a group of 1000; here's how we can test a ciphertext $C$ to see if its plaintext $P$ is $&gt; k$ or $&lt; k$ (for an arbitrary integer $k$); we would encrypt the value $k$ 999 times, and give those 999 ciphertexts, plus the ciphertext $C$ we're testing, to our method to find the top 10 - if the plaintext we're trying to deduce is $P &gt; k$, then $C$ will be one of the 10; if $P &lt; k$, it will not be.

Doing that technique, we can do binary search to reduce the possibilities for $P$ to a range of two values $k, k+1$; we can then homomorphically add $C$ to itself, and then perform the above test one last time to see if $2P$ is greater than or less than $2k+1$ - this gives us the final answer.

We hope that someone cannot do this, and so we hope that the problem you're asking to solve is infeasible.