[Feature Request] Addition, Multiplication about nufhe HOT 9 OPEN

I recently used a binary adder and multiplier for some experiments

The formatting is pretty bad, can you fix it? I would like to give it a look.

from nufhe.

If you mean implementing these operations via logic gates, there is an example implementation in numeric_functions.py. The problem is that even not considering the overheads, it turns out to be quite slow. The other way is to increase message space in ciphertexts, or connect with another FHE scheme working on integers - we are investigating the possibilities here, but there is nothing definite yet.

from nufhe.

I recently used a binary adder and multiplier for some experiments

from nufhe.

I created a more efficient binary adder here: https://github.com/InnovativeInventor/homomorphic-encryption/blob/master/poc.py (should take less steps).

from nufhe.

@InnovativeInventor What is the speed of modular addition of a long (2^15) vector of 32-64-bit integers?

from nufhe.

@jon-chuang Are you talking about addition modulo n, for a natural number n? I'm not quite understanding what you're asking me to benchmark here.

from nufhe.

@InnovativeInventor I was talking about modular addition. However, I have run your code and noted its still too slow even though GPU accelerated (5s for a single add). This must be the cost of bootstrapping on the gate level.

from nufhe.

@InnovativeInventor Actually, how certain are you that the code you wrote is the best performance you could get? For instance, could you get better performance if you used circuit rather than gate bootstrapping?

Actually, your circuit has depth n, but presumably you should be able to get a depth log n evaluation, am I right? Isn't there a more efficient alternative to ripple-carry addition as is implemented in your script? For instance, carry-lookahead adder?

Although, I am not too familiar with the underlying TFHE scheme.

from nufhe.

@jon-chuang A carry-lookahead adder will leak information, I think.

I'm not completely sure, but I think any efficiency improvements at the algorithm level will leak information or take longer (it may be possible to prove this, idk). Let me know if I'm wrong.

from nufhe.