Possible incompatibility with NTL 11.0.0 and higher

[yoshiko305]

I have recently done a clean installation of HElib with the newest version of HElib and NTL. I have written a simple program that has EncryptedArray rotate operation with specific parameters as shown below. However, the decryption result after rotation is incorrect, giving me random numbers instead of simple 0, 1, 0 as its result. This has given me a great difficulty until I tried a different version of NTL.

The program below DID NOT WORK correctly on NTL version 11.3.0 but WORKED correctly on NTL version 10.5.0.

I am not sure if this is a problem with the HElib or the NTL, but please resolve this issue as it could pose other problems in the future with other functionalities. Thank you.

long m=pow(2,14), p=20479, r=1;
long L=10; //Levels
long c=3; //key switching columns
long w=64; // Hamming weight of secret key
long d=0;
long security = 80;
ZZX G;

FHEcontext context(m, p, r);
buildModChain(context, L, c);
FHESecKey secretKey(context);
const FHEPubKey& publicKey = secretKey;
G = context.alMod.getFactorsOverZZ()[0];
secretKey.GenSecKey(w);
addSome1DMatrices(secretKey);
EncryptedArray ea(context, G);

int a = 100;
int b = 20;
long slots = context.zMStar.getNSlots();

vector <long> orig (slots, 0);
orig[a] = 1;
Ctxt cipher(publicKey);
ea.encrypt(cipher, publicKey, orig);

ea.rotate(cipher, -b);

vector <long> result;
ea.decrypt(cipher, secretKey, result);
cout << result[0] << endl;
cout << result[a-b] << endl;
cout << result[slots-1] << endl;

[victorshoup]

I've made some initial tests. It seems that your test program starts failing with ntl-11.1.0. I've also made some experiments to try to narrow down where the problem with ntl-11.1.0 may be.

It seems like this could be an NTL bug... I will continue working on it...

On Oct 24, 2018, at 4:58 AM, yoshiko305 notifications@github.com wrote:

I have recently done a clean installation of HElib with the newest version of HElib and NTL. I have written a simple program that has EncryptedArray rotate operation with specific parameters as shown below. However, the decryption result after rotation is incorrect, giving me random numbers instead of simple 0, 1, 0 as its result. This has given me a great difficulty until I tried a different version of NTL.

The program below DID NOT WORK correctly on NTL version 11.3.0 but WORKED correctly on NTL version 10.5.0.

I am not sure if this is a problem with the HElib or the NTL, but please resolve this issue as it could pose other problems in the future with other functionalities. Thank you.

long m=pow(2,14), p=20479, r=1 ;

long L=10; //Levels long c=3; //key switching columns long w=64; // Hamming weight of secret key long d=0 ;

long security = 80 ; ZZX G;

FHEcontext context (m, p, r);

buildModChain (context, L, c); FHESecKey secretKey (context);

const FHEPubKey& publicKey = secretKey; G = context.alMod.getFactorsOverZZ()[ 0 ]; secretKey.GenSecKey(w);

addSome1DMatrices (secretKey); EncryptedArray ea (context, G);

int a = 100 ;

int b = 20 ;

long slots = context.zMStar.getNSlots();

vector < long> orig (slots, 0 ); orig[a] = 1 ; Ctxt cipher (publicKey); ea.encrypt(cipher, publicKey, orig);

ea.rotate(cipher, -b);

vector < long

result; ea.decrypt(cipher, secretKey, result); cout << result[ 0 ] << endl; cout << result[a-b] << endl; cout << result[slots- 1] << endl; — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

[victorshoup]

Aha! The problem is a very basic one!! When m is a power of 2, helib makes direct calls to FFTFwd and FFTRev1.

These are undocumented, low-level routines that are subject to change, and should not generally be used by NTL clients. Since I wrote the new NTL routines and I also wrote this bit of helib code that called them, you would think I would have remembered to deal with this...but I didn't.

With NTL 11.1.0, the I/O behavior of these routines has changed: in helib, we will have to bit reverse the outputs of FFTFwd and bit reverse the inputs to FFTRev1, since NTL is no longer bit reversing anything.

It should be a simple change...

How did this happen? Two mistakes:

1) We don't have anything in our helib test suite with m=2^k 2) In NTL, I should have changed the names of these low-level routines, when I changed their semantics...but I was lazy, and I figured people should not be calling them...or maybe I planned to do it, but forgot...

I guess a third mistake is the perhaps the fact that we are using undocumented routines in the first place...maybe that is true, but I don't see any easy fix to that, if we want this software to have a chance to evolve and grow.

Anyway, I will implement the propose fix in helib, and then test everything again to confirm that this fixes the problem.

On Oct 24, 2018, at 7:58 AM, Victor Shoup shoup@cs.nyu.edu wrote:

I've made some initial tests. It seems that your test program starts failing with ntl-11.1.0. I've also made some experiments to try to narrow down where the problem with ntl-11.1.0 may be.

It seems like this could be an NTL bug... I will continue working on it...

On Oct 24, 2018, at 4:58 AM, yoshiko305 notifications@github.com wrote:

I have recently done a clean installation of HElib with the newest version of HElib and NTL. I have written a simple program that has EncryptedArray rotate operation with specific parameters as shown below. However, the decryption result after rotation is incorrect, giving me random numbers instead of simple 0, 1, 0 as its result. This has given me a great difficulty until I tried a different version of NTL.

The program below DID NOT WORK correctly on NTL version 11.3.0 but WORKED correctly on NTL version 10.5.0.

I am not sure if this is a problem with the HElib or the NTL, but please resolve this issue as it could pose other problems in the future with other functionalities. Thank you.

long m=pow(2,14), p=20479, r=1 ;

long L=10; //Levels long c=3; //key switching columns long w=64; // Hamming weight of secret key long d=0 ;

long security = 80 ; ZZX G;

FHEcontext context (m, p, r);

buildModChain (context, L, c); FHESecKey secretKey (context);

const FHEPubKey& publicKey = secretKey; G = context.alMod.getFactorsOverZZ()[ 0 ]; secretKey.GenSecKey(w);

addSome1DMatrices (secretKey); EncryptedArray ea (context, G);

int a = 100 ;

int b = 20 ;

long slots = context.zMStar.getNSlots();

vector < long> orig (slots, 0 ); orig[a] = 1 ; Ctxt cipher (publicKey); ea.encrypt(cipher, publicKey, orig);

ea.rotate(cipher, -b);

vector < long

result; ea.decrypt(cipher, secretKey, result); cout << result[ 0 ] << endl; cout << result[a-b] << endl; cout << result[slots- 1] << endl; — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

[shaih]

Pushed a fix, you should be good now.

[yoshiko305]

Thank you very much!! I will try it out!