[Feature Request] Addition, Multiplication

[lorepieri8]

Do you plan on supporting binary/decimal operations like addition and multiplication, besides supporting logic gates?

Thanks

[fjarri]

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.

[mominbuet]

I recently used a binary adder and multiplier for some experiments

[lorepieri8]

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.

[InnovativeInventor]

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

[jon-chuang]

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

[InnovativeInventor]

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

[jon-chuang]

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

[jon-chuang]

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

[InnovativeInventor]

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