snucrypto / HEAAN

Other
359 stars 94 forks source link

Bootstrapping a large number #23

Closed imtiyazuddin closed 5 years ago

imtiyazuddin commented 5 years ago

I want to know till what value I can go for bootstrapping. I have seen that for values less than 100 the bootstrapping is working fine, but beyond that the values are wrapping around some number not sure why. I think the wraparound depends on logp and the value you want to bootstrap. Kindly help me to understand this.

kimandrik commented 5 years ago

What values are you using? You can use for example values from the paper https://eprint.iacr.org/2018/153.pdf.

imtiyazuddin commented 5 years ago

sorry for the late reply, I tried to do bootstrapping for value 1000, but result was nowhere near 1000 when logQ was less before bootstrap (around 30). when I increased it to 40 result value after bootstrap was around 975. so can't we bootstrap a large value?? what parameters does it depend?? again sorry for late reply

kimandrik commented 5 years ago

If your value is 1000 (about 2^10), then it means that your inital logq should be at least logp + 10 (maybe it should be even bigger). I tried to bootstrap with parameters: logQ=1200, logN=16, bootstrapping parameters: logp = 23, logq=40, logQ = 1200, logT=2, logI=4, number of slots = 2^4.

Here is my code:

srand(time(NULL)); SetNumThreads(8); TimeUtils timeutils; Ring ring; SecretKey secretKey(ring); Scheme scheme(secretKey, ring);

timeutils.start("Key generating"); scheme.addBootKey(secretKey, logSlots, logq + logI); timeutils.stop("Key generated");

long slots = (1 << logSlots); complex* mvec = EvaluatorUtils::randomComplexArray(slots, 1000);

Ciphertext cipher; scheme.encrypt(cipher, mvec, slots, logp, logq);

cout << "cipher logq before: " << cipher.logq << endl; scheme.bootstrapAndEqual(cipher, logq, logQ, logT, logI); cout << "cipher logq after: " << cipher.logq << endl;

complex* dvec = scheme.decrypt(secretKey, cipher); StringUtils::compare(mvec, dvec, slots, "boot");

Results:

Start Key generating Key generated time = 22383.6 ms

cipher logq before: 40 cipher logq after: 650

mboot: 0 :(510.505,59.0125) dboot: 0 :(510.416,59.0207) eboot: 0 :(0.0892026,-0.00813816)


mboot: 1 :(823.536,166.283) dboot: 1 :(823.42,166.26) eboot: 1 :(0.115686,0.0224856)


mboot: 2 :(715.053,889.852) dboot: 2 :(715.038,889.794) eboot: 2 :(0.0141665,0.0586356)


mboot: 3 :(749.285,231.191) dboot: 3 :(749.167,231.175) eboot: 3 :(0.117784,0.0167897)


mboot: 4 :(635.082,824.305) dboot: 4 :(634.89,824.184) eboot: 4 :(0.192334,0.120461)


mboot: 5 :(92.0951,842.892) dboot: 5 :(91.9045,842.938) eboot: 5 :(0.190586,-0.0458966)


mboot: 6 :(483.041,464.966) dboot: 6 :(482.955,465.026) eboot: 6 :(0.0856202,-0.0601737)


mboot: 7 :(683.019,496.364) dboot: 7 :(682.96,496.302) eboot: 7 :(0.0587277,0.0619816)


mboot: 8 :(395.195,50.2628) dboot: 8 :(395.099,50.1769) eboot: 8 :(0.0961675,0.0858947)


mboot: 9 :(766.472,98.5755) dboot: 9 :(766.312,98.4703) eboot: 9 :(0.15977,0.105214)


mboot: 10 :(758.09,219.468) dboot: 10 :(758.019,219.486) eboot: 10 :(0.0713425,-0.0184042)


mboot: 11 :(594.974,724.924) dboot: 11 :(594.886,724.812) eboot: 11 :(0.0882235,0.111471)


mboot: 12 :(789.777,774.179) dboot: 12 :(789.675,774.051) eboot: 12 :(0.101307,0.128108)


mboot: 13 :(629.135,866.887) dboot: 13 :(629.024,866.888) eboot: 13 :(0.110946,-0.000438502)


mboot: 14 :(772.616,362.877) dboot: 14 :(772.456,362.879) eboot: 14 :(0.160788,-0.00177129)


mboot: 15 :(870.731,371.875) dboot: 15 :(870.763,371.844) eboot: 15 :(-0.0323168,0.0315327)

imtiyazuddin commented 5 years ago

Thank you so much :)