search

snucrypto / HEAAN

Other
359 stars 94 forks source link

Reason for bootstrapping speedup #7

Closed haochenuw closed 6 years ago

haochenuw commented 6 years ago

Hi, it seems bootstrapping in this library is faster than the original HEAANBOOT:

TestScheme::testBootstrap(15, 23, 29, 620, 5, 2);

Returns

Start SubSum SubSum time = 1982.59 ms

Start CoeffToSlot CoeffToSlot time = 6505.46 ms

Start EvalExp EvalExp time = 5553.62 ms

Start SlotToCoeff SlotToCoeff time = 3986.2 ms

So, the EvalExp is about 2 times faster, and similar for the linear parts. Can you explain what makes this speedup?

KyoohyungHan commented 6 years ago

Hi, we use CRT + NTT in this version. Previously we just use ZZX multiplication and reduce the result, and this was quite in efficieny. This change makes overall performance much better :)