Fast fully homomorphic arithmetic scheme? BFV = slow bootstrapping, TFHE = slow arithmetic

The BFV scheme is good for representing lots of integers inside a polynomial and we can even operate on them individually relatively fast. However, bootstrapping on BFV is infeasible, such that no library even implements it.

On the other hand, schemes like TFHE have very fast bootstrapping, but operate on gates. This paper is the newest I could find that finds a way to encode integers on the torus: https://www.mdpi.com/2078-2489/12/8/297 but it takes 0.9 seconds to multiply a 4-bit integer, which is too much. On BFV, I can not only multiply lots at the same time, but the multiplication takes much less time (around 80ms single-core) and the value of the coefficient (the plaintext modulus) can go to more than 1 million. I can even encode a 64-bit number in RNS form and multiply it in BFV on this one single 80ms polynomial multiplicaiton.

So, is there a better scheme that does a fast bootstrapping and work over word-sized representations of integers, not binary? (or maybe one that encodes in binary but makes artihmetic fast somehow).

There are more efficient implementations of TFHE than the one you quote. In particular, the company Zama has an implementation they call Concrete, which includes

• open source Rust code, which is also packaged as a rust "crate", and
• an integration with (part of) Numpy.

There are some benchmarks of the Rust code from ~ 2 years ago, where they claim ~30ms for multiplications. Unfortunately, it is not precisely clear to me from that document how many message bits they claim for the benchmark. I believe it is $\geq 5$, but it may be only $5$. Either way, this is of course much faster than ~.9s for 4 bit multiplications.

Note that you would still lose out on the SIMD-type qualities of BFV. Despite this, you might end up (practically) faster, as it appears Concrete has a GPU-accelerated backend (the aforementioned benchmarks were before this backend existed), so one could plausibly get a similar degree of parallelism via appealing to that.

Still though, provided I am interpreting the benchmarks correctly, this is a > 30x speedup from what you quote (before doing anything GPU-related, which is now an option), so is plausibly of interest.

Regarding BFV bootstrapping, the BGV cryptosystem has similar characteristics to BFV (they are both "fast arithmetic with SIMD + slow bootstrapping" schemes), and HElib's benchmarks contain sample code for BGV bootstrapping, which may be of interest to you.