search

nucypher / nufhe

NuCypher fully homomorphic encryption (NuFHE) library implemented in Python
https://nufhe.readthedocs.io/en/latest/
GNU General Public License v3.0
441 stars 53 forks source link

[Feature Request] Addition, Multiplication #18

Open lorepieri8 opened 4 years ago

lorepieri8 commented 4 years ago

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

Thanks

fjarri commented 4 years ago

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 commented 4 years ago

I recently used a binary adder and multiplier for some experiments

lorepieri8 commented 4 years ago

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 commented 4 years ago

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

jon-chuang commented 4 years ago

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

InnovativeInventor commented 4 years ago

@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 commented 4 years ago

@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 commented 4 years ago

@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 commented 4 years ago

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