While in public keys the fields ax and bx correspond to a and b in the paper, for Ciphertext it is the opposite: ax corresponds to b and bx corresponds to a (this essentially stems from C++ HEAAN). Since we are not preserving bit-to-bit compatibility anymore, the order may be changed - it will help with comparing the code and the paper.

It's probably a good idea to make the early integration of the moduli chunking technique used to speedup keyswitch by more than twice for large parameter sets.

Also, is there going to be GPU support just like for nuFHE? Why is the reference implementation HEAAN not SEAL?

HEAAN uses modulo integers in range (-q/2 ... q/2] (where q is a power of 2). Switching to the range used by computers ([-q/2 ... q/2)) will simplify some of the functions. The question is, is this range essential for the algorithm to work?

Currently there are BigInt, BinModuloInt and Polynomial() scattered throughout the code. They need to be made constants or functions, so that they could be changed in a single place. Especially BigInt, in case we want to try using fixed size integers (although note that we might need several different sizes for the best efficiency).

In "Homomorphic Encryption for Arithmetic of Approximate Numbers" and "Improved Bootstrapping for Approximate Homomorphic Encryption", the encryption key is stored and applied modulo q_L (params.log_lo_modulus in the code). But in C++ HEAAN it is stored and applied modulo q_L * P (params.log_lo_modulus + params.log_hi_modulus), with plaintexts scaled appropriately. Fixing that seems to drop the number of retained bits somewhat. What's the deal here?

The log_precision field in Ciphertext really just corresponds to the scale of the number inside. The actual precision drops because of embedding/unembedding (which we perhaps can account for, since they happen on plaintext), and because of slow precision loss in each multiplication. According to Andrey Kim:

If you have magnitude estimations of initial values you can estimate the initial precision, then after every multiplication similar to unencrypted case precision becomes worse by one bit (actually a little more than one bit). So you can estimate the guaranteed output precision. It will be almost similar to unencrypted estimations. But similar to unencrypted case practical results are normally much better than theoretical estimates.

Some way to estimate the final precision of an algorithm may be useful.

It is possible to avoid modulo 2^n polynomials altogether and go full RNS. See "A Full RNS Variant of Approximate Homomorphic Encryption" by Cheon et al (2018) for details. May obsolete issue #1 and issue #2.

Fields of Params (polynomial length, modulus etc) should be derived based on the security parameter. Perhaps the LWE security estimator can be used.

Currently we need to write code like

x = add(a, b)
y = mul(mul_key, x, c)

which can become hard to read for large algorithms (see e.g. exp2pi()). Would be nice to have an ability to do something like

res = vm(mul_key, conj_key, ...) do
    (a + b) * c
end

This may need a macro though, not sure if it can be implemented just as a function.

Note that one will have to match log_precision and log_cap of results, applying rescale_to()/mod_down_to() as appropriate.

Currently circshift() for ciphertexts only supports left rotation. Right rotation should be easy to add by taking a modulo plen.

Two ways are possible:

1. Store some of the values in Montgomery representation. Good candidates are the keys and perhaps bootstrap values? We can prevent mistakes by creating a RNSPolynomialTransformedM type in addition to RNSPolynomialTransformed, and making sure that only operators non-M + non-M = non-M, M + M = M, non-M * M = non-M and M * M = M are defined.

2. If non-M * non-M is necessary somewhere after step 1, Barrett reduction can be used there.

3. More convenient moduli can be chosen (close to 2^64, with small number of bits set). This will require support from DarkIntegers.

It will be more helpful for testing and development if operators that combine several ciphertexts and/or keys checked that those actually have the same parameter sets and match each other. Constructors must enforce the consistency of values as well. There have been some improvements in that respect lately, but there is still work to do.

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 e0ecd8d 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.

May be a good idea to test advanced algorithms (including bootstrapping) using pseudo-ciphertexts with unencrypted fixed-precision numbers. This way it is easy to see what is happening with cap exhaustion, what values we get and so on (and also the coinciding bits measurements in API tests will be more accurate).

Note that this will require creating an abstract ciphertext class and accessor methods instead of just using Ciphertext's fields directly.

The paper "Improved Bootstrapping for Approximate Homomorphic Encryption" by Cheon et al (2018) describes an improved bootstrapping technique. At the moment of this writing it is not yet implemented in the C++ HEAAN. Perhaps it will resolve the current bootstrapping issues (see issue #1).