search

homenc / HElib

HElib is an open-source software library that implements homomorphic encryption. It supports the BGV scheme with bootstrapping and the Approximate Number CKKS scheme. HElib also includes optimizations for efficient homomorphic evaluation, focusing on effective use of ciphertext packing techniques and on the Gentry-Halevi-Smart optimizations.
https://homenc.github.io/HElib
Other
3.14k stars 765 forks source link

How many levels are consumed while doing addTwoNumbers function #232

Open Jyun-Neng opened 6 years ago

Jyun-Neng commented 6 years ago

I try to use Test_binaryArith to do different bit size binary addition. In my opinion, doing n-bit addition should consume n levels by using ripple carry adder.

For example: a=(a_1, a_0), b=(b_1, b_0), where a, b are 2-bit numbers and (a_1, a_0), (b_1, b_0) are its binary representation, respectively. And the addition result is sum=(sum_2, sum_1, sum_0). sum_0 = a_0 + b_0 sum_1 = a_1 + b_1 + (a_0 b_0) (consumes 1 level) sum_2 = (a_1 b_1) (a_0 b_0) (consumes 2 levels)

But in fact, Test_binaryArith.cpp consumes fewer levels than above method. For example, running 5-bit addition consumes 3 levels, running 8-bit addition consumes 4 levels. I think that this program does not use the ripple carry adder, but I don't know what method does this program use.

shaih commented 6 years ago

addition, multiplication, comparisons, all of these take O(log n) levels for n-bit numbers. You can look in the code to see how it is done (the comparison code is a bit easier to decipher).

AlexDanDuna commented 6 years ago

@shaih: Doesn't this document also detail how binary arith & comparison work in HElib? :) https://eprint.iacr.org/2018/202