Some question about bootstrapping

[Ldisi]

Hi, i am confused about bootstrping. In Test_bootstrping.cpp , it choose the first set of parameters( smallest m). The result is good, but Securty level < 0. So i choose latter set of parameters to make Securty level > 64, However ,the result is far from good. Could someone tell me how to make bootstrpe working, THX!!

[jlhcrawford]

Hi @Ldisi can you please specify the set of parameters that you used to run the bootstrapping test? I just ran the test with security=68.7 and it worked as expected.

Note that Test_bootstrapping has been superseded by Test_fatboot and Test_thinboot.

Also the test you are trying to run is a legacy test and is planned to be phased out in the future. These tests have been ported to a new googletest framework found in HElib/src/tests. To build these tests you need to run cmake with the flag -DENABLE_TEST=ON.

To run a specific test from the HElib/build directory run ./bin/runTests --gtest_filter="*Test_bootstrapping*". Running that command without the gtest filter will run all tests located in the HElib/src/tests directory.

Additionally a paper that explains the theory of bootstrapping in HElib can be found here https://eprint.iacr.org/2014/873

[Ldisi]

Hi @jlhcrawford My parameters are : p = 2 , r =21 , c =3 , L= 600, nthreads = 1, { p, phi(m), m, d, m1, m2, m3, g1, g2, g3,ord1,ord2,ord3, c_m} = { 2, 24000, 31775, 20, 41, 775, 0, 6976, 24806, 0, 40, 30, 0, 100} My security level : about 110. But the runtime is too long, Maybe 30 min per recrypt operation. I have tried Test_fatboot, but it looks just like bootstrapping test except bootstrapping test has Initial parameters. Waiting for your advice. THX!

[victorshoup]

Can you set the verbose switch (noPrint=0) and give us the output?

Also, I'm afraid that working with such a large plaintext modulus of 2^21 may be inherently impractical. But I'd like to see the verbose output anyway.

[victorshoup]

For these parameters, 30 minutes per recryption is not unrealistic. If you are not using fully packed slots in your application, you should look at the thin bootstrapping procedure.

[Ldisi]

Of course, @victorshoup ， This is my code , i just choose a specific set of parameters in Test_bootstrping.cpp and you are right, r=21 is too large ,so i set 1 /* Copyright (C) 2012-2017 IBM Corp.

• This program is Licensed under the Apache License, Version 2.0
• (the "License"); you may not use this file except in compliance
• with the License. You may obtain a copy of the License at
• http://www.apache.org/licenses/LICENSE-2.0
• Unless required by applicable law or agreed to in writing, software
• distributed under the License is distributed on an "AS IS" BASIS,
• WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
• See the License for the specific language governing permissions and
• limitations under the License. See accompanying LICENSE file. */

/* Test_bootstrapping.cpp - Testing the recryption procedure */

#if defined(unix) || defined(__unix) || defined(unix) #include <sys/time.h> #include <sys/resource.h> #endif

#include <NTL/ZZ.h> #include <NTL/fileio.h> #include <NTL/BasicThreadPool.h> NTL_CLIENT #include #include "EncryptedArray.h" #include "EvalMap.h" #include "powerful.h" #include "matmul.h" #include "ArgMap.h" #include"time.h" static bool noPrint = false; static bool dry = false; // a dry-run flag static bool debug = 0; // a debug flag static int scale = 0;

extern FHESecKey* dbgKey;

// #define DEBUG_PRINTOUT #include "debugging.h" extern long printFlag;

static long mValues[][14] = { //{ p, phi(m), m, d, m1, m2, m3, g1, g2, g3,ord1,ord2,ord3, c_m} { 2, 24000, 31775, 20, 41, 775, 0, 6976, 24806, 0, 40, 30, 0, 100}, // m=(5^2)*{31}41 m/phim(m)=1.32 C=88 D=2 E=2 }; #define num_mValues (sizeof(mValues)/(14sizeof(long)))

#define OUTER_REP (1) #define INNER_REP (1)

void TestIt(long idx, long p, long r, long L, long c, long skHwt, int build_cache=0) { Vec mvec; vector gens; vector ords;

long phim = mValues[idx][1]; long m = mValues[idx][2]; assert(GCD(p, m) == 1);

append(mvec, mValues[idx][4]); if (mValues[idx][5]>1) append(mvec, mValues[idx][5]); if (mValues[idx][6]>1) append(mvec, mValues[idx][6]); gens.push_back(mValues[idx][7]); if (mValues[idx][8]>1) gens.push_back(mValues[idx][8]); if (mValues[idx][9]>1) gens.push_back(mValues[idx][9]); ords.push_back(mValues[idx][10]); if (abs(mValues[idx][11])>1) ords.push_back(mValues[idx][11]); if (abs(mValues[idx][12])>1) ords.push_back(mValues[idx][12]);

if (!noPrint) { cout << "*** TestIt"; if (isDryRun()) cout << " (dry run)"; cout << ": p=" << p << ", r=" << r << ", L=" << L << ", c=" << c << ", m=" << m << " (=" << mvec << "), gens="<<gens<<", ords="<<ords << endl; cout << "Computing key-independent tables..." << std::flush; } setTimersOn(); setDryRun(false); // Need to get a "real context" to test bootstrapping

double t = -GetTime(); FHEcontext context(m, p, r, gens, ords); if (scale) { context.scale = scale; }

context.zMStar.set_cM(mValues[idx][13]/100.0); buildModChain(context, L, c,/willBeBootstrappable=/true, /t=/skHwt);

if (!noPrint) { std::cout << "security=" << context.securityLevel()<<endl; std::cout << "# small primes = " << context.smallPrimes.card() << "\n"; std::cout << "# ctxt primes = " << context.ctxtPrimes.card() << "\n"; std::cout << "# bits in ctxt primes = " << long(context.logOfProduct(context.ctxtPrimes)/log(2.0) + 0.5) << "\n"; std::cout << "# special primes = " << context.specialPrimes.card() << "\n"; std::cout << "# bits in special primes = " << long(context.logOfProduct(context.specialPrimes)/log(2.0) + 0.5) << "\n"; std::cout << "scale=" << context.scale<<endl; }

// FIXME: The willBeBootstrappable flag is a hack, used to bypass the // issue that buildModChain must be called BEFORE the context is made // botstrappable (else the "powerful" basis is not initialized correctly.)

context.makeBootstrappable(mvec, /t=/skHwt, build_cache); t += GetTime();

if (!noPrint) { cout << " done in "<<t<<" seconds\n"; cout << " e=" << context.rcData.e << ", e'=" << context.rcData.ePrime << ", t=" << context.rcData.skHwt << "\n "; context.zMStar.printout(); } setDryRun(dry); // Now we can set the dry-run flag if desired

long p2r = context.alMod.getPPowR();

for (long numkey=0; numkey<OUTER_REP; numkey++) { // test with 3 keys

t = -GetTime(); if (!noPrint) cout << "Generating keys, " << std::flush; FHESecKey secretKey(context); FHEPubKey& publicKey = secretKey; secretKey.GenSecKey(); // A +-1/0 secret key addSome1DMatrices(secretKey); // compute key-switching matrices that we need addFrbMatrices(secretKey); if (!noPrint) cout << "computing key-dependent tables..." << std::flush; secretKey.genRecryptData(); t += GetTime(); if (!noPrint) cout << " done in "<<t<<" seconds\n";

zz_p::init(p2r); zz_pX poly_p = random_zz_pX(context.zMStar.getPhiM()); PowerfulConversion pConv(context.rcData.p2dConv->getIndexTranslation()); HyperCube<zz_p> powerful(pConv.getShortSig()); pConv.polyToPowerful(powerful, poly_p); ZZX ptxt_poly = conv<ZZX>(poly_p); PolyRed(ptxt_poly, p2r, true); // reduce to the symmetric interval

#ifdef DEBUG_PRINTOUT dbgKey = &secretKey; // debugging key and ea dbgEa = context.rcData.ea; // EA for plaintext space p^{e+r-e'} dbg_ptxt = ptxt_poly; context.rcData.p2dConv->ZZXtoPowerful(ptxt_pwr, dbg_ptxt); vecRed(ptxt_pwr, ptxt_pwr, p2r, true); if (dbgEa->size()>100) printFlag = 0; // don't print too many slots #endif

ZZX poly2; Ctxt c1(publicKey);

secretKey.Encrypt(c1,ptxt_poly,p2r);

Ctxt c_const1(publicKey); secretKey.Encrypt(c_const1, ZZX(1), p2r);

c1.multiplyBy(c_const1);

for (long num=0; num<INNER_REP; num++) { // multiple tests with same key publicKey.reCrypt(c1); secretKey.Decrypt(poly2,c1);

if (ptxt_poly == poly2) cout << "GOOD\n";
else if (!isDryRun()) { // bootsrtapping error
  cout << "BAD\n";

#ifdef DEBUG_PRINTOUT conv(poly_p,poly2); HyperCube<zz_p> powerful2(pConv.getShortSig()); cout << "decryption error, encrypted "; printVec(cout, powerful.getData())<<endl;

  pConv.polyToPowerful(powerful2, poly_p);
  cout << "                after reCrypt ";
  printVec(cout, powerful2.getData())<<endl;
  long numDiff = 0;
  for (long i=0; i<powerful.getSize(); i++) 
    if (powerful[i] != powerful2[i]) {
      numDiff++;
      cout << i << ": " << powerful[i] << " != " << powerful2[i]<<", ";
      if (numDiff >5) break;
    }

#endif exit(0); } } } if (!noPrint) printAllTimers(); resetAllTimers(); #if (defined(unix) || defined(__unix) || defined(unix)) struct rusage rusage; getrusage( RUSAGE_SELF, &rusage ); if (!noPrint) cout << " rusage.ru_maxrss="<<rusage.ru_maxrss << endl; #endif }

/******************************************************************** ********************************************************************/

//extern long fhe_disable_intFactor; extern long fhe_force_chen_han;

int main(int argc, char *argv[]) { ArgMap amap;

long p=2; long r=1; long c=3; long L=600; long N=0; long t=0; long nthreads=1;

long seed=0; long useCache=1;

amap.arg("p", p, "plaintext base");

amap.arg("r", r, "exponent"); amap.note("p^r is the plaintext-space modulus");

amap.arg("c", c, "number of columns in the key-switching matrices"); amap.arg("L", L, "# of bits in the modulus chain"); amap.arg("N", N, "lower-bound on phi(m)"); amap.arg("t", t, "Hamming weight of recryption secret key", "heuristic"); amap.arg("dry", dry, "dry=1 for a dry-run"); amap.arg("nthreads", nthreads, "number of threads"); amap.arg("seed", seed, "random number seed"); amap.arg("noPrint", noPrint, "suppress printouts"); amap.arg("useCache", useCache, "0: zzX cache, 1: DCRT cache");

amap.arg("force_bsgs", fhe_test_force_bsgs); amap.arg("force_hoist", fhe_test_force_hoist);

// amap.arg("disable_intFactor", fhe_disable_intFactor); amap.arg("chen_han", fhe_force_chen_han);

amap.arg("debug", debug, "generate debugging output"); amap.arg("scale", scale, "scale parameter");

amap.parse(argc, argv);

if (seed) SetSeed(ZZ(seed));

SetNumThreads(nthreads);

clock_t start, finish; start =clock(); for (long i=0; i<(long)num_mValues; i++) if (mValues[i][0]==p && mValues[i][1]>=N) { TestIt(i,p,r,L,c,t,useCache); break; } finish = clock(); cout<<" time cost: "<<(finish-start)/CLOCKS_PER_SEC<<"secs"<<endl; return 0; }

[Ldisi]

This is the output: *** TestIt: p=2, r=1, L=600, c=3, m=31775 (=[41 775]), gens=[6976 24806], ords=[40 30] Computing key-independent tables...security=92.7366 small primes = 6 ctxt primes = 11 bits in ctxt primes = 613 special primes = 4 bits in special primes = 239 scale=10 WARNING: prime power factorization recommended for bootstrapping done in 303.481 seconds e=11, e'=3, t=100 m = 31775, p = 2, phi(m) = 24000 ord(p)=20 generator 6976 has order (== Z_m^) of 40 generator 24806 has order (== Z_m^) of 30 Generating keys, computing key-dependent tables... done in 88.1785 seconds WARNING: noise bound exceeded in encryption GOOD
AAA_LinearTransform1: 86.8431 / 1 = 86.8431 [/home/zengke/FHE/HElib-master/src/recryption.cpp:500] AAA_LinearTransform2: 86.4138 / 1 = 86.4138 [/home/zengke/FHE/HElib-master/src/recryption.cpp:520] AAA_embeddingLargest: 158.886 / 3397 = 0.0467725 [/home/zengke/FHE/HElib-master/src/norms.cpp:109] AAA_extractDigitsPacked: 1126.39 / 1 = 1126.39 [/home/zengke/FHE/HElib-master/src/recryption.cpp:509] AAA_preProcess: 2.36243 / 1 = 2.36243 [/home/zengke/FHE/HElib-master/src/recryption.cpp:409] BasicAutomorphPrecon: 1.75162 / 4 = 0.437905 [/home/zengke/FHE/HElib-master/src/matmul.cpp:63] BlockMatMul1DExec: 32.6597 / 2 = 16.3298 [/home/zengke/FHE/HElib-master/src/matmul.cpp:1448] BluesteinFFT: 581.497 / 87378 = 0.00665496 [/home/zengke/FHE/HElib-master/src/bluestein.cpp:136] CRT_reconstruct: 29.0416 / 730 = 0.039783 [/home/zengke/FHE/HElib-master/src/PAlgebra.cpp:640] CRT_reconstruct: 0.705978 / 729 = 0.00096842 [/home/zengke/FHE/HElib-master/src/PAlgebra.cpp:640] CompMod: 1.21659 / 730 = 0.00166657 [/home/zengke/FHE/HElib-master/src/PAlgebra.cpp:604] CompMod: 0.127566 / 729 = 0.000174988 [/home/zengke/FHE/HElib-master/src/PAlgebra.cpp:604] Decrypt: 0.247524 / 1 = 0.247524 [/home/zengke/FHE/HElib-master/src/FHE.cpp:918] DoubleCRT: 149.265 / 1421 = 0.105042 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:471] DoubleCRT: 205.191 / 3441 = 0.0596312 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:413] FFT: 176.236 / 1696 = 0.103913 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:71] FFT: 176.172 / 25424 = 0.00692935 [/home/zengke/FHE/HElib-master/src/CModulus.cpp:438] FFT: 317.114 / 41744 = 0.00759663 [/home/zengke/FHE/HElib-master/src/CModulus.cpp:424] FFT: 317.232 / 5187 = 0.061159 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:52] FFT_remainder: 29.9729 / 41744 = 0.000718016 [/home/zengke/FHE/HElib-master/src/CModulus.cpp:429] FFT_remainder: 1.49224 / 25424 = 5.86941e-05 [/home/zengke/FHE/HElib-master/src/CModulus.cpp:443] GenKeySWmatrix: 86.9877 / 90 = 0.96653 [/home/zengke/FHE/HElib-master/src/FHE.cpp:834] KS_loop: 137.37 / 2143 = 0.0641018 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:180] KS_loop_1: 31.9122 / 2143 = 0.0148914 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:187] KS_loop_2: 20.2992 / 2143 = 0.00947234 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:190] KS_loop_3: 32.0047 / 2143 = 0.0149345 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:194] KS_loop_4: 21.2648 / 2143 = 0.0099229 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:197] MatMul1DExec: 5.10116 / 6 = 0.850193 [/home/zengke/FHE/HElib-master/src/matmul.cpp:666] addCtxt: 77.5783 / 2479 = 0.0312942 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:931] addPart: 47.9194 / 5926 = 0.0080863 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:665] addPrimes: 199.529 / 1748 = 0.114147 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:334] addPrimes_5: 204.811 / 1747 = 0.117236 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:317] automorph: 43.2802 / 140 = 0.309144 [/home/zengke/FHE/HElib-master/src/matmul.cpp:96] automorph: 1.89411 / 57 = 0.03323 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:1517] breakIntoDigits: 206.362 / 783 = 0.263553 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:296] buildLinPolyCoeffs: 0.012739 / 900 = 1.41544e-05 [/home/zengke/FHE/HElib-master/src/EncryptedArray.cpp:562] buildLinPolyCoeffs: 0.51651 / 901 = 0.000573263 [/home/zengke/FHE/HElib-master/src/EncryptedArray.cpp:562] buildLinPolyCoeffs_invert: 0.093266 / 1 = 0.093266 [/home/zengke/FHE/HElib-master/src/EncryptedArray.cpp:571] buildLinPolyCoeffs_invert: 0.000451 / 1 = 0.000451 [/home/zengke/FHE/HElib-master/src/EncryptedArray.cpp:571] canonicalEmbedding: 156.922 / 3397 = 0.0461942 [/home/zengke/FHE/HElib-master/src/fft.cpp:82] canonicalEmbedding: 80.1328 / 1707 = 0.0469436 [/home/zengke/FHE/HElib-master/src/fft.cpp:58] canonicalEmbedding: 2.10818 / 44 = 0.0479131 [/home/zengke/FHE/HElib-master/src/fft.cpp:71] do_mul: 151.459 / 10845 = 0.0139658 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:169] embedInSlots: 30.3321 / 730 = 0.0415508 [/home/zengke/FHE/HElib-master/src/PAlgebra.cpp:578] embedInSlots: 0.910658 / 729 = 0.00124919 [/home/zengke/FHE/HElib-master/src/PAlgebra.cpp:578] extractDigitsPacked: 1126.39 / 1 = 1126.39 [/home/zengke/FHE/HElib-master/src/recryption.cpp:634] extractDigitsThin: 1076.45 / 20 = 53.8225 [/home/zengke/FHE/HElib-master/src/recryption.cpp:781] frobeniusAutomorph: 13.7154 / 20 = 0.68577 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:1606] iFFT: 205.751 / 20210 = 0.0101806 [/home/zengke/FHE/HElib-master/src/CModulus.cpp:454] iFFT_division: 48.9395 / 20210 = 0.00242155 [/home/zengke/FHE/HElib-master/src/CModulus.cpp:519] keySwitchPart: 318.012 / 779 = 0.408231 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:619] modDownToSet: 635.677 / 1526 = 0.416565 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:356] mul_BlockMatMul1DExec: 142.105 / 2 = 71.0527 [/home/zengke/FHE/HElib-master/src/matmul.cpp:1472] mul_MatMul1DExec: 31.1516 / 2 = 15.5758 [/home/zengke/FHE/HElib-master/src/matmul.cpp:775] multByConstant: 56.7383 / 1700 = 0.0333755 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:1390] multByConstant: 3.90532 / 20 = 0.195266 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:1415] multLowLvl: 373.412 / 721 = 0.517909 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:1173] multiplyBy: 982.707 / 721 = 1.36298 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:1249] privateAssign: 16.4932 / 3130 = 0.0052694 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:278] randomize: 28.194 / 2417 = 0.0116649 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:991] randomize_stream: 8.70106 / 3689795 = 2.35814e-06 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:1018] reCrypt: 1302.43 / 1 = 1302.43 [/home/zengke/FHE/HElib-master/src/recryption.cpp:359] reLinearize: 665.305 / 828 = 0.803508 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:559] repack: 4.30744 / 1 = 4.30744 [/home/zengke/FHE/HElib-master/src/recryption.cpp:690] skEncrypt: 0.958268 / 3 = 0.319423 [/home/zengke/FHE/HElib-master/src/FHE.cpp:978] smartAutomorph: 57.7835 / 57 = 1.01374 [/home/zengke/FHE/HElib-master/src/Ctxt.cpp:1558] toPoly: 269.022 / 5145 = 0.0522881 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:669] toPoly_CRT: 50.6728 / 5145 = 0.00984894 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:730] toPoly_FFT: 215.267 / 5145 = 0.04184 [/home/zengke/FHE/HElib-master/src/DoubleCRT.cpp:710] unpack: 45.6013 / 1 = 45.6013 [/home/zengke/FHE/HElib-master/src/recryption.cpp:637] upgrade: 220.205 / 16 = 13.7628 [/home/zengke/FHE/HElib-master/src/matmul.cpp:371] rusage.ru_maxrss=5380688 time cost: 1698secs

[victorshoup]

Thanks for the info. This does not look unreasonable. Bootstrapping is pretty slow. As I mentioned, for your application, you may want to use thin bootstrapping. I'm not sure what you are trying to achieve.

[Ldisi]

THX , What I want is to recrypt Ctxt many times in binary domain(p=2, r=1)

[victorshoup]

Sure. But what data is in the slots? Is to just bits? Then look at thin recrypt. It is much faster (maybe 10x for these parameters).

[Ldisi]

Yes, I convert the field of real Numbers to binary. I wonder why thin recrypt run much faster than other one.

[victorshoup]

It is designed to exploit the fact that the slots contain only numbers (0 or 1) and not field elements (elements of GF(2^20) in your case). Normal (fat) bootstrapping has to do a lot more work to deal with this general case. You can look at our bootstrapping paper on eprint. Look at section 7 for performance data on fat vs thin.

[Ldisi]

Of course, I will read this paper carefully later, thank you for your contributions