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.11k stars 759 forks source link

Is there a cheap method to do zero-one masking? #464

Open lifematrix opened 2 years ago

lifematrix commented 2 years ago

Hello, everyone,

I am new to Homomorphic Encryption and try to use HElib to implement a complex neural convolutional network. Retrieving an entry on the certain position of the cipher text vectoris a very common and useful operation. It can be implemented by multiplying a zero-one vector, but very expensive.

I read Shai Halevi's paper Algorithms in HElib which discussed zero-fill shift. The paper gave me the feeling that the shift operation can be achived with a lower cost.

I found HElib really provided zero-fill shift operation, so a masking can be achieved by two shifts and one rotation, i.e., suppose position is i (zero-based), shift left i, shift right n-1, and rotate right n-1-i. However, the experimental code I wrote showed the shift operation is more expensive both in noise budget (like multipication) and speed (like rotation).

So, is there a cheap method to do zero-one masking in HElib? Or do I have any misunderstanding?

Thank you very much,

Steven

fionser commented 2 years ago

zero-filling is noting but just multiplying zero-one vectors then rotation.

lifematrix commented 2 years ago

@fionser Thank you very much for your reply. I could understand the approach you described. But multiplication will cost the noise budget. So I want to find a cheaper one.

I just read the source code of HELib. It really did mask vector multiplying with type zzX type in rotate function of EncryptedArray.cpp. I guess maybe it is cheaper rather than multiplying a plaintext mask vector that is encoded from a mask vector of float?

tzukpolinsky commented 2 years ago

i found that multiply ctxt in a zeroed ptxt where ptxt[i]=1 is the best way to create masking for all slots!=i

cause except in a very low security levels contexts or m init var is power of 2, you have a large number of slots, and the amounts of shifts needed generates much more noise than one multiplication, but thats base on trail and error so i dont have mathematics to backup this routine