3
$\begingroup$

I have two integers $x,y$ which are encrypted using a homomorphic cryptosystem, probably Paillier.
I am looking for a (one-party) protocol that, given $enc(x)$ and $enc(y)$, returns a bit $b = 1 \iff x \geq y$ (b plaintext) without knowledge of the private key.
I found several solutions for Yao's Millionaires' Problem, however most of them are for two parties and require that each party knows the plaintext value of their input.
Is this possible with the constraint that both integer values are positive and small ($0 \leq x,y \leq 1000$) and complexity is not the main issue?
Right now I have something like this: Create a set containing the numbers $0,1,2,...,1000$. For each entry $i$ calculate $(enc(x) - enc(y) - enc(i)) * r$ then shuffle the results and check if one entry equals zero. (Lets assume there is an algorithm available that answers "equals zero" requests).

$\endgroup$
5
$\begingroup$

What you are asking for is impossible, because it would immediately break the cryptosystem.

Let's assume for a moment, that such a function exists and we know how it works. And we get a challenge ciphertext $c = enc(x)$. We know the public key, because it's public. And if we assume the set of messages to be $0,1,\dots,1000$, we then just encrypt $500$ and then apply the function to get $x \geq 500$. If it is true, we apply the algorithm to $c$ and $enc(750)$ and otherwise to $c$ and $enc(250)$. This is just a binary search, and this way we can efficiently find out what $x$ is - without knowing the decryption key. And that would mean, there is no security at all.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.