I hope to calculate the median of a set of ciphertexts

FHE Questions
1

Hello,
I now hope to calculate the median of a set of ciphertexts in the ciphertext state. Can this be done ?

2

You should be able to do that, but I am not sure it can be done efficiently.

To compute the median of an array of encrypted numbers using homomorphic encryption, follow these steps:

  1. Homomorphically sort the array of ciphertexts.
  2. Return the middle element (the encrypted median value).

Note that array size, number magnitude, and number type can impact performance.

Maybe, you can explore existing FHE transpilers to simplify code translation into FHE-compatible form.

1 Like
3

To add to @Caesar comment. You cannot do it efficiently in BGV/BFV/CKKS due to the lack of an encrypted gt or lt operator. One could use scheme switching in order to do that using one of the DM schemes but it is woefully inefficient.
You can look at the new openFHE transpiler examples repository to see code that manipilates ciphertext with comparison operations. We don’t have a median example but looking at that code you could see how you could easily sort a list of integers and select the mid element. -Dave

1 Like
4

Thank you for your answer, so is there an effective function for sorting ciphertext?

5

@dcousins, I had a look at the repository you provided but I am not sure to understand. For example in the file shortest_path_iterative/select_path.cc, at line 20:

bool chooseNew = (newPath.cost < oldPath.cost);

Is this a comparison between ciphertexts?

I was expecting to find an example using the OpenFHE library, so I am a bit lost.

@crazyRobert I guess you would have to pick your favorite sorting algorithm and apply it to your list of ciphertexts.

6

the transpiler converts C++ code functions (no floats) into encrypted digital circuits. Comparison is a supported function.
you encrypt and decrypt data that way. Openfhe is one of the backends.
Sorry if that confuses you.
the line of code you cite when encrypted would generate a single bit CT that is the result of the comparison of the two integer CT ( the cost field of the Path structure).

If you were to require staying with ckks and floating point numbers then you need to do it a totally different way. I;d suggest then looking at this example that does a single comparison.. Note it is computationally intensive.

7

thanks a lot for the explanation, it is much clearer now.