I’ve heard that zama is going to represent big numbers by smaller 3-bit numbers. So suppose we have 2 16-bit numbers composed of 3-bit LWE a,b,c,d numbers and also e,f,g,h
abcd
efgh
How do we do carry addition on those?
Hi Guerlando,
Indeed, the homomorphic computations over large integers are done using multiple LWE blocks. For instance, by using the default types for 16-bit integers in Concrete, the parameters are: 8 blocks encrypting messages encoded over 2-bits, along with 2 supplementary bits dedicated to the carry management. The initial cleartext message is first decomposed following a basis equals to 2^2 = 4. Each block encrypts then a part of this decomposition.
Following your example, let’s assume 4 LWE blocks of 4 bits each, with 4 bits of carry.
The addition gives:
a b c d
+ e f g h
---------------
a+e b+f c+g d+h
Since each block has a carry buffer, the carry of the addition is eventually stored there. Once one of the carry buffer is almost full, the second part consists in “propagating the carry” all along the blocks. In a nutshell, this is done using PBSes to extract the carry at one block and apply an homomorphic addition with the next block. The carry of the last block is simply thrown way since we are working modulus 2^16. Note that you can use an alternative representation (called CRT), where this operation is much more simple and efficient.
If you want more information about this process (and the large homomorphic integers in general), you can have a look on this FHE.org meeting and to the associated technical report.