It seems that the multiplication or dot product of ciphertexts with ciphertexts cannot exceed 16 bits in their calculation results. I would like to know what causes this limitation and how it can be modified to increase the computational upper limit?Any insights or guidance would be greatly appreciated!
Hi, it’s because multiplications are implemented with table lookups, and table lookups can only be done up to 16-bit integers
If you want to work with large integers, you should implement some kind of encoding using arrays (e.g., use tensor of 32 binary values to represent integers in a binary storage) and implement algorithms that work on those tensors (e.g., binary multiplication).
Hope this helps!
If I am not wrong are using this identity for table lookups x.y= 1/4(( x+y)^2-(x-y)^2),
so effectively we are adding cipher texts and doing a table look up for the square function ,
But we have a native multiplication between two TGSW cipher texts ,which could be thought of as column of internal product between TGSW and TLWE cipher text and which can further described as a external product between decomposition w.r.t to gadget matrix for TLWE polynomials and TGSW cipher text(In short internal product expressed as external product between TLWE and TGSW)
Never the less cipher text ,multiplication between GGSW cipher texts is possible ,why are we not implementing it that way
Hello @Laser_beam,
You are not wrong the current status of the implementation is exactly what you describe. As you said the multiplication between two lwe ciphertext could be implemented as you said using the GGSW x GLWE but that need to apply a circuit boostrap on lwe ciphertext before the multiplication which in theory is more costly than what we have implemented.