Bootstrapping problems for full-slot ciphertexts

[fjarri]

The bootstrapping procedure that was ported from C++ HEAAN is described in "Improved Bootstrapping for Approximate Homomorphic Encryption" by Cheon et al (2018), section 2.2.

It works for non-full-slot ciphertexts (that is, slots < 2^(polynomial_length - 1)), or at least, it works just as it does in C++ HEAAN. There is still a significant precision loss, although perhaps, that is what's expected.

There is a number of problems/unexplained questions.

1. In commit e0ecd8d5577578d3f4f23633c78420c6d1d0dd91 an optional log_precision argument to add_const() was removed, which was used in exp2pi(). The intention seemed to be to override the precision of the constant with that used in BootContext. But if you add a constant with a precision different from cipher.log_precision to a ciphertext, you'll get trash results, which can be checked by testing add_const() separately. Nevertheless, somehow it worked, and the precision was even slightly better, 6 to 13 bits retained instead of 6 to 10.

2. In exp2pi(), in the line

   cipher23 = add(cipher23, cipher01)

   cipher23 and cipher01 have different log_precision/log_cap, so technically cannot be added. Nevertheless, they are added in HEAAN C++, and the way it works, add() used the first ciphertext's parameters for the results. Since in this port add is stricter, I had to add mod_down_to() for cipher01, which didn't seem to change the results.

3. If one changes the bootstrap test to use a full-slot ciphertext (so, log_slots=7), there are multiple mismatches of precision and cap in add and mul functions. I tried to alleviate them by making ciphertexts compatible if needed by dropping cap/precision with

   function make_compatible(cipher1::Ciphertext, cipher2::Ciphertext; keep_precision::Bool=false)
       if !keep_precision
           p1 = cipher1.log_precision
           p2 = cipher2.log_precision
           if p1 < p2
               cipher2 = rescale_by(cipher2, p2 - p1)
           elseif p2 < p1
               cipher1 = rescale_by(cipher1, p1 - p2)
           end
       end
   
       q1 = cipher1.log_cap
       q2 = cipher2.log_cap
   
       if q1 < q2
           cipher2 = mod_down_by(cipher2, q2 - q1)
       elseif q2 < q1
           cipher1 = mod_down_by(cipher1, q1 - q2)
       end
   
       cipher1, cipher2
   end

   but there were still other problems with this code path, so I'm not sure how well it helped. Leaving it for reference here.

4. It is unclear what is the expected behavior of bootstrap(). How high can it be expected to raise log_cap? How does chosen log_precision for BootContext affect things (and why is it taken as log_cap + 4, specifically, in C++ HEAAN)? Can we predict the precision/cap drop in exp2pi() and eval_exp() depending on ciphertexts and boot context parameters, and deduce the optimal way of performing the calculation?

5. Finally, full-slot ciphertext bootstrapping simply does not work, even with the use of make_compatible(), because I could not find the set of parameters where the log_precision of a ciphertext wouldn't drop below 0 at some point (in exp2pi()). Strangely enough, in C++ HEAAN it does drop below zero (which, in my understanding, would mean that the ciphertext contains complete rubbish), and yet the result is accurate within 2 to 11 bits. Weird.

[fjarri]

6. What does log_i parameter do in eval_exp()?

7. The bootstrap precision dropped very slightly after commit 5d7f956e6d94c802216663e9f998f4deea985044 , even though it seems to be the correct way to handle mod_up_to() (and the same way C++ code works).

[fjarri]

8. For commit ffc95912ffaf9c94cea9253bae7da346b3dbad02, the additional range during decomposition in BootContext constructor for rpvec and rpvecInv is params.log_lo_modulus + 2 * log_plen (essentially, comes from, C++ HEAAN). Not sure what is the second log_plen needed for - the tests seem to work fine with just params.log_lo_modulus + log_plen (no assertions in polynomial.jl are hit, so we're staying within ranges), but then again, perhaps there are some conditions where this limit is necessary.