AlexanderViand
commented
6 years ago I know this question is pretty old, but maybe it's still helpful to your or others stopping by:
I used to have a decent reference for the "three-for-two" trick but I can't find it right now. The idea is that one can take three binary numbers a,b,c and combine them into two binary numbers x,y so that a+b+c = x + 2*y.
We calculate each bit i of x as x[i] = a[i] + b[i] + c[i] and for y we have y[i] = a[i] b[i] + a[i] c[i] + b[i] * c[i] where + is XOR and * is AND. I think the usual formulation of this (at least for y) is actually with OR instead of XOR but since it also works with XOR, it's easier to use that here. The reason this works is because we're effectively computing the "propagate" and the "carry" bits, just for two additions at the same time.
With a tree of 3-for-2 operations one can combine k numbers down to two (log2(k) longer) numbers using only log-base-1.5(k) multdepth and then do a single addition for log2(new bit length) multdepth for a total of log1.5(k) + log2(newbitlength). Compare this with using a tree of standard additions, which would be roughly log2(k) * log2(newbitlength).
About the multithreading: I've run into some bugs in another of the binaryArith.cpp functions that only appeared when threading was enabled so maybe it's intentional, but of course only the developers can really answer that.
About the edit: Yes, there's a potential for optimisation there, e.g. in the multiplication we can drop the partial products for the bits there plaintext input is 0 and we save one level of multiplicative depth because the partial products are now no longer products. I've actually implemented that in my own fork of HElib, maybe I'll submit a PR for it. With addition I'm sure there's also some potential for optimisation since we gain some additional info about which positions can generate carries but I don't see as direct a way of using that to optimise things.
I'd like to use the new binary arithmetic and comparison functions that have been recently introduced, but I've got a few questions.
The first would be if using addManyNumbers is preferable over consecutively using addTwoNumbers (I read that the former uses the 3-for-2 method, but where could I find more information about it? Is it more efficient to do multiple additions this way? Or is this actually similar to the "Three-way multiplications' otimization mentioned in Appendix E of the AES implementation article?).
My second question would be why in the 'addManyNumbers' method the multi-threading part is commented out? Was it unintentional to comment it out or is that portion of code not thread-safe?
EDIT: I'd also want to ask: is it theoretically possible to implement addConstant/multiplyByConstant equivalents for bit-by-bit encrypted numbers? I assume yes :D, but I'd appreciate a confirmation.
Also, I've got a last question, but this is a little off-topic: could someone,please, point me where I could learn how to choose parameters (with and without bootstrapping) ? I know I could use 'params.cpp' for this matter, but I'd like to understand the reasoning behind those choices.
Thank you very, very much to all of you who are spending your time helping me out!