1
$\begingroup$

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)

$\endgroup$
12
  • $\begingroup$ I've included the sorting swap in this answer Representing a function as FHE circuit. Read the note below the sorting swap. Also. Bubble sort is not a good idea for FHE since it requires very high level. A better one is network sorting. If nothing is clear, indicate. $\endgroup$ – kelalaka Feb 17 '20 at 14:56
  • $\begingroup$ Also, note that they are not totally implemented Buble sort in FHE, they used a noisy operation that left 30% of the result is in the incorrect place randomly that you need to correct after decryption. $\endgroup$ – kelalaka Feb 17 '20 at 14:58
  • $\begingroup$ @kelalaka okay thank you i'll look into it but do you know how they were able to conclud the result by looking only at the MSB? $\endgroup$ – Daniel K Feb 17 '20 at 15:06
  • $\begingroup$ MSB is used in the comparison, it contains the information that the number is positive or not. Subtract two signed numbers and look at the MSN to figure out their relative order. In FHE it is encrypted so you need such a circuit. The comparison is also included in my answer. $\endgroup$ – kelalaka Feb 17 '20 at 15:10
  • $\begingroup$ @kelalaka ahh okay thank you I understood why they used the MSB but another thing I didn't understand is what you mean by 'Bubble sort is not a good idea for FHE since it requires very high level' what is meant by high level and why isn't it good? $\endgroup$ – Daniel K Feb 17 '20 at 15:13