Encrypted comparison

[lastmjs]

Other operations, such as encrypted comparison, sorting, or regular expressions, are in most cases not feasible to evaluate on encrypted data using this technology.

Sorry, I'm new to this. Is the above implying that encrypted comparison is not possible with SEAL? As in, do I absolutely have to look elsewhere for this type of functionality?

Given a simple example, like sending two encrypted numbers to a server and subtracting them, would I somehow be able to know if the encrypted result was equal to 0 without decrypting it on the server? One way that I could think of doing this is by sending an encrypted 0 from the client, and then doing the comparison on the server. Am I thinking about this correctly?

[kimlaine]

There is a huge difference between doing equality check (is encrypted number equal to zero) and comparison (is the encrypted number positive). How these might be done depends strongly on the encryption scheme you use (SEAL implements BFV and CKKS).

BFV allows encrypting modular integers where comparison is very challenging to do but equality test is reasonable. For equality, you can subtract two encrypted integers (or vectors of them); the result is zero mod plain_modulus if they are equal and otherwise non-zero. Now, if plain_modulus is prime, using Fermat's little theorem you can exponentiate to power plain_modulus-1. The result will be an encrypted 0 precisely when the two inputs matched, and 1 otherwise. Then just compute 1-Enc(result) to flip the bit. This can make sense if plain_modulus is reasonably small, otherwise you'll end up needing very large parameters to support the exponentiation. Note that the server does not learn the unencrypted result, but only an encrypted result, which the data owner has to decrypt. In some protocols it suffices to not compute the exponentiation, and instead return the difference of the two values (possibly randomized by a random multiplicand modulo plain_modulus). In this case, however, your signal for equality is zero and non-equality a random integer modulo plain_modulus, which may be hard to use for any further encrypted computations.

CKKS allows encrypting fixed-precision real numbers where the comparison function can be approximated (see e.g. https://eprint.iacr.org/2019/1234). This is probably not very practical if you need high-precision comparison near zero.

[lastmjs]

So will the server alone never be able to branch based off of an encrypted equality check or comparison? Will the server always have to return the encrypted result to the client, where the client can decrypt the result and than make a branching decision?

[kimlaine]

Right. It's impossible to truly branch on encrypted data; otherwise the branch would leak information about the encrypted data, which is not supposed to be the case. What is possible though, is evaluating both branches and filtering out the desired one. This is used for example in https://arxiv.org/abs/1909.08362.

[lastmjs]

Ah, thanks for the insights!

[Shaedul]

Hello @kimlaine @lastmjs , I need help to understand the equality check technique between two encrypted integers. I want to quote your statement :

BFV allows encrypting modular integers where comparison is very challenging to do but equality test is reasonable. For equality, you can subtract two encrypted integers (or vectors of them); the result is zero mod 'plain_modulus' if they are equal and otherwise non-zero.

I have two encrypted integer
a = encryptedzero
b = encryptedone
How can I get is it equal or not? is it possible to get True or false? If you give a small example based on your statement for equality check will be highly appreciated.

[WeiDaiWD]

It does not yield true or false. The equality check result is in encrypted form. One equality check algorithm, subtraction, gives encrypted zero (equal) or encrypted non-zero (unequal). The other algorithm, Fermat's little theorem, gives encrypted zero (equal) or encrypted one (unequal).

Subtraction algorithm:

Ciphertext encrypted_a, encrypted_b, encrypted_equality;
Evaluator::sub(encrypted_a, encrypted_b, encrypted_equality);
Plaintext equality;
Decryptor::decrypt(encrypted_equality, equality);

Now equality is 0 if a and b are equal and is non-zero otherwise.

Fermat's little theorem (following the above code block):

Evaluator::exponentiate_inplace(encrypted_equality, plaintext_modulus - 1, relin_keys);
Plaintext new_equality;
Decryptor::decrypt(encrypted_equality, new_equality);

Now new_equality is 0 if a and b are equal and is 1 otherwise.

[Shaedul]

@WeiDaiWD Thank you for your great example and I am clear. I am working on genome data. Actually based on this equality result I will perform another computation. So I just want to know if I decrypt the new_equality variable to get the equality check result on the server-side. is it mean that I provide my secret key to the cloud side? Because I want to keep encrypted the individual's genome data on the cloud during the analysis. After analysis individuals will receive the encrypted result and able to see the result using the secret key that I can make sure a secure analysis of sensitive data. Hope your feedback will be a solution to my misunderstanding or guidelines to go ahead.

[WeiDaiWD]

If you share the secret key with the server, there is no point to encryption anything at the beginning. And we don't recommend to have the client decrypt that and send it back to server. What you want to do is computing new_equality * X + (plain_one - new_equality) * Y which is an encrypted method to compute new_equality ? X : Y.

[Shaedul]

@WeiDaiWD Thank you very much for your support and guidelines

[kai-chi]

Hi @WeiDaiWD @kimlaine,

Is it possible to apply the Fermat's little theorem to a vector in order to batch encrypted comparison?
Following the example, I changed encrypted_equality to a vector of ints but the process starts to consume all available memory and dies when executing exponentiate_inplace. It works fine for a scalar.

[WeiDaiWD]

exponentiate_inplace is extremely memory inefficient (we should have explained this in comment). It creates a vector of exponent number of same ciphertexts and calls multiply_many. If you look at the implementation of multiply_many, you can see that we are simply trying to perform a series of ciphertext multiplication with the fewest depth. Potentially, it can avoid copying the ciphertext exponent times, which is what you need to get rid of the massive memory consumption. Well, still, avoid choosing a large plain_modulus.

[kai-chi]

Thanks a lot for a quick response!
In that case, do you have any tips how to vectorize equality checks? One-by-one does the job but it's gonna be extremely inefficient for larger datasets

[WeiDaiWD]

Vectorization is done at the ciphertext layer. Each Ciphertext encrypts a vector of values. exponentiate_inplace raise all of the underlying values of one ciphertext to the given exponent. For example, if you have Ciphertext ct_x, ct_y that encrypt (x0, x1, x2, ..., x1023) and (y0, y1, y2, ..., y1023), then running evaluator::sub_inplace(ct_x, ct_y) will give you (x0-y0, x1-y1, x2-y2, ..., x1023-y1023) in ct_x. Now you need to compute evaluator::exponentiate_inplace(ct_x, plain_modulus-1) for the Fermat's little theorem. Finally the result will be a vector of powers encrypted in the single ciphertext ct_x. The catch here is that you need to implement a different evaluator::exponentiate_inplace that does not require a massive amount of memory.

[kai-chi]

Thanks for a thorough response. I've made it work all the way until the evaluator::exponentiate_inplace step and then it obviously fails. I'm new to SEAL so it'd be great to shirk from re-implementing the library. Do you happen to know any other idea for equality check that can be batched using the current implementation?

[WeiDaiWD]

What I meant by "implement a different evaluator::exponentiate_inplace" is not re-implementing the library. They are multiple algorithms to compute exponentiation, for example, sequentially multiplying the value itself, square-and-multiply, etc. You just need to pick one that gives a low multiplicative depth, and then use Evaluator::square(...) or Evaluator::multiply(...) to implement the algorithm. I don't know another way to check equality beside the Fermat's little therom.

[jimouris]

@WeiDaiWD I am trying your suggestion with Fermat's little theorem but it does not work as expected. I am setting x = Enc(13), y = Enc(14), and z = Enc(13) and I am doing two comparisons, x == y and x == z. I have attached my code below:

#include <iostream>
#include <fstream>

#include "examples.h"

using namespace seal;
using namespace std;

int main(int argc, char** argv) {
  EncryptionParameters parms(scheme_type::bfv);
  size_t poly_modulus_degree = 4096, plaintext_modulus = 1024;
  parms.set_poly_modulus_degree(poly_modulus_degree);
  parms.set_coeff_modulus(CoeffModulus::BFVDefault(poly_modulus_degree));
  parms.set_plain_modulus(plaintext_modulus);
  SEALContext context(parms);
  print_parameters(context);
  KeyGenerator keygen(context);
  SecretKey secret_key = keygen.secret_key();
  PublicKey public_key;
  RelinKeys relin_keys;
  keygen.create_public_key(public_key);
  keygen.create_relin_keys(relin_keys);

  Encryptor encryptor(context, public_key);
  Evaluator evaluator(context);
  Decryptor decryptor(context, secret_key);

  Ciphertext equality_enc, x_enc, y_enc, z_enc;
  Plaintext plain_x("13"), plain_y("14"), plain_z("13");
  Plaintext decrypted_result;
  encryptor.encrypt(plain_x, x_enc);
  encryptor.encrypt(plain_y, y_enc);
  encryptor.encrypt(plain_z, z_enc);

  // Check x_enc == y_enc
  evaluator.sub(x_enc, y_enc, equality_enc); // equality_enc = x_enc - y_enc
  evaluator.exponentiate_inplace(equality_enc, plaintext_modulus - 1, relin_keys);
  decryptor.decrypt(equality_enc, decrypted_result);
  cout << "x == y? : 0x" << decrypted_result.to_string() << endl;

  // Check x_enc == z_enc
  evaluator.sub(x_enc, z_enc, equality_enc); // equality_enc = x_enc - z_enc
  evaluator.exponentiate_inplace(equality_enc, plaintext_modulus - 1, relin_keys);
  decryptor.decrypt(equality_enc, decrypted_result);
  cout << "x == z? : 0x" << decrypted_result.to_string() << endl;

  return EXIT_SUCCESS;
}

In decrypt, I would expect to get 1 and 0 but this isn't the case, I am getting a lot of polynomials:

.....  + 353x^22 + 183x^21 + 20Ax^20 + 101x^19 + 3DBx^18 + 26Ex^17 + 230x^16 + 36x^15 + 92x^14 + 2E1x^13 + 270x^12 + 3BCx^11 + 28Bx^10 + E3x^9 + 157x^8 + 178x^7 + 145x^6 + 22Cx^5 + 13Ex^4 + 343x^3 + 15Dx^2 + F0x^1 + 3F4

I appreciate your help!

[WeiDaiWD]

@jimouris You are evaluating a ciphertext to its 1023-th power. The best algorithm will require 10 multiplicative depth. EncryptionParameters that you have chosen do not support such a large depth. So your decryption fails with wrong results. If you follow the examples in SEAL, you can call Decryptor::invariant_noise_budget method to see whether decryption will fail. Then keep doubling poly_modulus_degree until the results are correct.

[jimouris]

@WeiDaiWD Awesome, thank you for the quick response!

[hdk0102]

@lastmjs I also struggled from the same need. Here I link two papers that may provide you with a good insight :)

• A great paper showing you how you can compare two encrypted numbers, by Kim (link)
• A recent paper showing you how you can pair such technique to your specific need, by Kang (link)