The error of using HomNAND operations to implement HomAND

[NanXiao]

Hi Leo,

Greetings from me!

I use your FHEW library to implement HomAND operation:

void HomAND(LWE::CipherText* res, const FHEW::EvalKey& EK, const LWE::CipherText& ct1, const LWE::CipherText& ct2 ) {
               LWE::CipherText u;

               FHEW::HomNAND(&u, EK, ct1, ct2);
               FHEW::HomNAND(res, EK, u, u);  
}

Sometimes I find the result of HomAND is not correct, for example, both inputs are 0, but the calculation result is 1, not 0. To debug it, I store all sec.key, ev.key, u and res in the file.

When the bug occurs again, I find the u is correct, because the result of using “cmd/dec sec.key u“ is 1, so the first HomNAND operation is correct. While the second HomNAND with both input parameters are 1 generates wrong result: 1.

I can’t find the reproduce condition of this issue, but it indeed occurs sometimes. So do you have time and interest to investigate this issue? If you need it, I will transfer all related files.

Thanks very much in advance!

Best Regards Nan Xiao

[lducas]

Dear Nan,

can you let me know at what frequency the bugs happen ?

Please note that correctness in FHEW is only guaranteed with a certain probability (quite close to 1 thought, please refer to the paper). The failure probability analysis is done for inputs that are independant though, and using the same input twice in HomNAND is likely to increase the failure probability.

May I suggest another approach to implementing AND gates (as well as OR and NOR gates directly) ? The reason we did NAND gate only is to provide a minimal set of universal gates, but the most efficient way to to a AND is not to do two NANDs.

In FHEW.cpp, line 164

  void HomNAND(LWE::CipherText* res, const EvalKey& EK, const LWE::CipherText& ct1, const LWE::CipherText& ct2) {
    LWE::CipherText e12;
    for (int i = 0; i < n; ++i)
      e12.a[i] = (2*q - (ct1.a[i] + ct2.a[i])) % q;
e12.b = (13 * q / 8) - (ct1.b + ct2.b) % q;

if you change the constant (13 * q / 8) to other appropriate constants, you can obtains other gates. Note that 13q/8 is the same as 5q/8 modulo q, yet, in c we need to maintain positive result to ensure the modulo q is done properly. From what I remember, replacing 5q/8 by q/8 provides the AND gate as desired. I'll leave it to you to find the right constant.

If you decide to implement all other gates in this way, I'll be happy to review your code and accept a pull request.

[NanXiao]

Hi Leo,

Thanks very much for your response!

can you let me know at what frequency the bugs happen ?

It is hard to describe. But I can reproduce it using the following method. The code is like this:

#include <iostream>
#include <cstdlib>
#include <cassert>
#include "FHEW.h"

using namespace std;

/* Secret & evaluation keys */
LWE::SecretKey LWEsk;
FHEW::EvalKey EK;

void SaveSecretKey(const LWE::SecretKey* LWEsk, char* filepath) {
  FILE * f;
  f = fopen(filepath, "wb"); // wb -write binary
  if (f == NULL) {
    cerr << "Failed to open "<< filepath <<  " in Write-Binary mode .\n";
    exit(1);
  }
  //cerr << "Writing Secret key to "<< filepath <<  ".\n";
  fwrite(LWEsk, sizeof(LWE::SecretKey), 1, f);
  fclose(f);
}

void SaveEvalKey(const FHEW::EvalKey *EK, char* filepath) {
  FILE * f;
  f = fopen(filepath, "wb"); // wb -write binary
  if (f == NULL) {
    cerr << "Failed to open "<< filepath <<  " in Write-Binary mode .\n";
    exit(1);
  }
  cerr << "Writing Evaluation key to "<< filepath <<  ".\n";
  FHEW::fwrite_ek(*EK, f);
  fclose(f);
}

void SaveCipherText(const LWE::CipherText* ct, char* filepath){
  FILE * f;
  f = fopen(filepath, "wb"); // wb -write binary
  if (f == NULL){
    cerr << "Failed to open "<< filepath <<  " in Write-Binary mode .\n";
    exit(1);
  }
  //cerr << "Writing CipherText to "<< filepath <<  ".\n";
  assert(fwrite(ct, sizeof(LWE::CipherText), 1, f));
  fclose(f);
}

int main(int argc, char *argv[]) {
    FHEW::Setup();
    LWE::KeyGen(LWEsk);
    FHEW::KeyGen(&EK, LWEsk);
    SaveSecretKey(&LWEsk, "sec.key");
    SaveEvalKey(&EK, "ev.key");

    for (;;) {
        LWE::CipherText ct1, ct2, u, res;
        LWE::Encrypt(&ct1, LWEsk, 0);
        LWE::Encrypt(&ct2, LWEsk, 0);
        FHEW::HomNAND(&u, EK, ct1, ct2);
        FHEW::HomNAND(&res, EK, u, u);
        int dec = LWE::Decrypt(LWEsk, res);
        if (dec != 0) {
            SaveCipherText(&u, "u.ct");
            SaveCipherText(&res, "res.ct");
            assert(0);
        }
    }

    return 0;  
}

The core part is main() function:

int main(int argc, char *argv[]) {
    FHEW::Setup();
    LWE::KeyGen(LWEsk);
    FHEW::KeyGen(&EK, LWEsk);
    SaveSecretKey(&LWEsk, "sec.key");
    SaveEvalKey(&EK, "ev.key");

    for (;;) {
        LWE::CipherText ct1, ct2, u, res;
        LWE::Encrypt(&ct1, LWEsk, 0);
        LWE::Encrypt(&ct2, LWEsk, 0);
        FHEW::HomNAND(&u, EK, ct1, ct2);
        FHEW::HomNAND(&res, EK, u, u);
        int dec = LWE::Decrypt(LWEsk, res);
        if (dec != 0) {
            SaveCipherText(&u, "u.ct");
            SaveCipherText(&res, "res.ct");
            assert(0);
        }
    }

    return 0;  
}

At the beginning, the program stores LWEsk and EK after initialization:

FHEW::Setup();
LWE::KeyGen(LWEsk);
FHEW::KeyGen(&EK, LWEsk);
SaveSecretKey(&LWEsk, "sec.key");
SaveEvalKey(&EK, "ev.key");

Then is the dead-loop for test:

for (;;) {
    LWE::CipherText ct1, ct2, u, res;
    LWE::Encrypt(&ct1, LWEsk, 0);
    LWE::Encrypt(&ct2, LWEsk, 0);
    FHEW::HomNAND(&u, EK, ct1, ct2);
    FHEW::HomNAND(&res, EK, u, u);
    int dec = LWE::Decrypt(LWEsk, res);
    if (dec != 0) {
        SaveCipherText(&u, "u.ct");
        SaveCipherText(&res, "res.ct");
        assert(0);
    }
}

In every iteration, the ct1 and ct2 are initialized through LWE::Encrypt, then after calling FHEW::HomNAND twice, the decryption of res should be 0.

About running about one hour, the program will assert() since the decryption of res is 1 instead of 0. But u, the result of first FHEW::HomNAND operation, is 1. So it seems in this iteration, the first FHEW::HomNAND generates correct result, while the second FHEW::HomNAND not.

Could you help to check this issue? Thanks very much in advance!

Best Regards Nan Xiao

[lducas]

So this fails after about 1000 to 5000 trials, do I read this correctly ? This seems to corroborate the theory that this failure is due to the lack of independence, invalidating the hypothesis failure proba analysis of the paper.

Nan, how do you feel about the following fix :

• we throw an error whenever both input of the HomNAND gates are the same ciphertext, saying that the gate should not be used this way.
• we provide all three other gates directly, by replacing the constant 5q/8, by q/8, 3q/8 and 7q/8.

I think q/8 is AND, 7q/8 is OR, 3q/8 is NOR, but please double-check !

Best -- Leo

[NanXiao]

@lducas

So this fails after about 1000 to 5000 trials, do I read this correctly ?

Yes, you are right! Maybe more times.

we provide all three other gates directly, by replacing the constant 5q/8, by q/8, 3q/8 and 7q/8.

I think this is a good method. I will try to test it, thanks very much!

[NanXiao]

@lducas

I think q/8 is AND, 7q/8 is OR, 3q/8 is NOR, but please double-check !

Yes, I have tested the truth-table, and all above three gates are correct! Please excuse for my greedy requirements, it is also possible implement XOR gate through modifying the constant? Thanks in advance!

[lducas]

it is also possible implement XOR gate through modifying the constant?

Hum, that would be more involved, and unless one change a few parameters, that would lead to much larger failure probability.

Note that if you are OK switching to another FHE you can get more flexibility and more speed : https://github.com/tfhe/tfhe

[NanXiao]

Hum, that would be more involved, and unless one change a few parameters, that would lead to much larger failure probability.

One workaround is to use HomNAND implement HomXOR:

void HomXOR(LWE::CipherText* res, const FHEW::EvalKey& EK, const LWE::CipherText& ct1, const LWE::CipherText& ct2 ) {
    LWE::CipherText u1, u2, u3;

    HomNAND(&u1, EK, ct1, ct2);
    HomNAND(&u2, EK, ct1, u1);
    HomNAND(&u3, EK, ct2, u1);
    HomNAND(res, EK, u2, u3);
  }

Since there is no same parameters in HomNAND() function, I think the failure probability is near 0. Is it right? Thanks!

[lducas]

I think you can make it using just three gates since: A xor B = (A and ~B) or (~A and B). Note that the not gate (noted ~) comes for free in FHEW.

[NanXiao]

@lducas

Note that the not gate (noted ~) comes for free in FHEW.

Now the method of getting not I can think of is inputting the same input into HomNAND gate, but it will cause potential issue we have discussed.

[lducas]

Oh no ! Not gate is just: (a,b) -> (-a, -b + q/4) If I am not mistaken...

[NanXiao]

@lducas The following is my code, and it meets the truth-table.

void HomNOT(LWE::CipherText* res, const EvalKey& EK, const LWE::CipherText& ct) {
    for (int i = 0; i < n; ++i)
      res->a[i] = -ct.a[i];
    res->b  =  -ct.b + q/4;
  }

Could you help to double-check it? Thanks!

[lducas]

I would do minor changes to ensure proper representation mod q.

void HomNOT(LWE::CipherText* res, const EvalKey& EK, const LWE::CipherText& ct) {
    for (int i = 0; i < n; ++i)
      res->a[i] = (q - ct.a[i]) % q;
    res->b  =  (-ct.b + 5*q/4) % q;
  }

[lducas]

@NanXiao : is PR #15 satisfying ? May I close this ?

[NanXiao]

@lducas Yes, you can close it, thanks!