Is there a way to combine n 1-slot ciphers into a single cipher with n slots?

snucrypto / HEAAN

Other

359 stars 94 forks source link

Is there a way to combine n 1-slot ciphers into a single cipher with n slots? #30

Closed jayavanth closed 5 years ago

kimandrik commented 5 years ago

Suppose you have n 1-slot ciphertexts: ctxt_1(x_1), ..., ctxt_n(x_n).

You can create n different plaintexts: ptxt_1(1,0,0,....,0), ptxt_2(0,1,0,0,....,0), ptxt_3(0,0,1,0,0,....,0), ..., ptxt_n(0,0,...,0,0,1) each encoding a vector of size n (suppose n is a power of two, otherwise take 1<< ceil(logn) ) with all 0 except single 1.
Now you can multiply each of ctxt_i(x_i) by ptxt_i. The result is a ciphertext ctxt(0,0,...,x_i,...,0).
Then you can add them all together.

kimandrik commented 5 years ago

You can treat a 1-slot ciphertext ctxt(x) as a ciphertext ctxt(x,x,x,.....,x) with n slots, where n is power-of-two.

If you have for example 4-slot ciphertext ctxt(x,y,z,t), you can treat it as a ciphertext ctxt(x,y,z,t,x,y,z,t,...,x,y,z,t), with n slots, where n>=4 is power-of-two

jayavanth commented 5 years ago

Thanks, @kimandrik. Is it possible to do the same with leftShifts and add instead of the last two steps?

Create a new ctxt(0,0,0,0,0,0...0) and add ctxt(0,0,0,....,x_1)
Left shift ctxt(0,0,0,0....x_1, 0) and now add the 2nd element ctxt(0,0,0,...,x_2)
Left shift ctxt(0,0,0,0...0, x_1, x_2, 0), and now add the 3rd element ctxt(0,0,0,...,x_3) repeat till x_n

jayavanth commented 5 years ago

Also, how does multiplying a ciphertext by plaintext work? Is it a multByConst?

kimandrik commented 5 years ago

You mean multiply ctxt(x_1,x_1,...,x_1,x_1) by ptxt(0,0,...,0,1) to obtain ctxt(0,0,...,0,x_1), then left rotate it to obtain ctxt(0,0,...,0,x_1,0), then multiply ctxt(x_2,x_2,...,x_2,x_2) by ptxt(0,0,...,0,1) to obtain ctxt(0,0,...,0,x_2), add it to ctxt(0,0,...,0,x_1,0) to obtain ctxt(0,0,...,0,x_1,x_2), then left rotate it to obtain ctxt(0,0,...,0,x_1,x_2,0), etc? This takes n multiplications by constant and n leftrotations. Multiplication by constant is much faster than left rotation, so the first method should be much faster.

How to multiply for example by (1,0,0,...,0): 1) in one of the latest commit we added a method multByConstVec(Ciphertext& res, Ciphertext& cipher, complex cnstVec, long logp). So you even don't need to encode (1,0,0,...,0). 2) Or you can encode (1,0,0,...,0) to ZZ with ring.encode and then use Scheme::multByPoly method

jayavanth commented 5 years ago

Ah sweet, that makes sense. Thanks!