# algorithmic scheme to compare these two number encrypted using paillier cryptosystem

I have been going through https://eprint.iacr.org/2006/287.pdf (Conjunctive, Subset, and Range Queries on Encrypted Data by Dan boneh)

I am trying to implement the paillier system to create a secure tunnel for gps related data on cloud.

There is a simple implementation of the system in python @https://github.com/mikeivanov/paillier

I am currently stuck at understanding how to code a comparision scheme for any two encrypted values

• Paillier encryption falls short of the goals of the first reference cited. The closest I see to "a comparision scheme for any two encrypted values" that Paillier encryption allows is that a party holding the private key can be submitted queries prepared from Enc(A) and Enc(B) by another party that does not hold the private key, that will determine if A<B, without A or B being disclosed to either party. That's easy. But applying that "to create a secure tunnel for gps related data on cloud" looks quite artificial.
– fgrieu
Apr 22, 2018 at 15:01

This is to be expected as what you are trying to do is impossible with standard Paillier encryption. To see this, first note that Paillier encryption is IND-CPA. We are now going to construct an attacker that wins the IND-CPA game with probability $1$ assuming they can relieably check for equality of two encrypted messages and thus proves that a scheme supporting this cannot be IND-CPA and thus Paillier can't actually allow for this.
Let $=_p:\mathcal C\times \mathcal C\to\mathbb B$ be a predicate that returns true for a given pair $(c_1,c_2)$ iff $D(c_1)=D(c_2)$ that is if the decryptions of the given ciphertexts are equal. This predicate models the functionality you are trying to realize. Now let's start with the IND-CPA game:
1. We pick two arbitrary distinct messages $m_0,m_1$ of the same length (the exact values don't matter) and send them to the challenger.
2. We receive $c_b=E(m_b)$ with $b$ being randomly chosen by the challenger. We compute $c_0'=E(m_0)$ on our own using the public key.
3. If $c_b=_pc_0'$ we return $b=0$, else we return $b=1$.
As $c_b=_pc_0'$ if and only if $b=0$ due to the construction of $c_0'$ and the way $=_p$ works, we always win the game with probability $1$ which yields the "advantage" $0.5$ which is clearly non-negligble and thus breaks IND-CPA security.