I've read in a pdf written by Ayantika Chatterjee and Khin Mi Mi Aung whose title is "Fully Homomorphic Encryption in Real World Applications" that it is possible to implement a bubble sort algorithm using certain Fully homomorphic libraries to be able to compare and sort messages while they are encrypted, here is a snippet of the pdf:
The FHS circuit depends on two main operations: subtraction operation and decision making based on the subtraction result. Fully Homomorphic subtraction, which is implemented by performing homomorphic addition of one ciphertext with 2’s complement of another ciphertext. For two plaintext numbers a and b, subtraction can be computed as: a − b = a + 2’s complement of b Now a homomorphic subtraction of a' and b' which are the encryptions of a and b respectively is computed using the homomorphic addition as follows: a' − b' = a' + Encrypt(2’s complement of b) The 2’s complement of b in the encrypted domain is obtained as follows: Encrypt((2's complement of b), pk) = b' ⊕ Encrypt(11 . . . 1, pk) ⊕ Encrypt(1, pk)
They also say that:
The MSB (most significant bit) of the substraction output is further fed to the decision making module as a selection line. The following equations represent how the swap operation takes place between two elements A[i] and A[i + 1] depending on MSB (represented here as bt): temp = bt ∗ A[i] + (1 − bt) ∗ A[i + 1] A[i + 1] = (1 − bt) ∗ A[i] + bt ∗ A[i + 1] A[i] = temp
So they make very clear that its the MSB of the substraction that determines which encrypted message is the biggest/smallest.
So my question is how were they able to determine that is only the MSB which determines the answer because i know that if we have the number 2 which is smaller than the number 3 after encryption we don't have a guarantee that Enc(2) is smaller than Enc(3)