# Meaning of “integers modulo 4 ” in “Fully homomorphic encryption modulo Fermat numbers” scheme

My question refers to the paper "Fully homomorphic encryption modulo Fermat numbers" by Antoine Joux. On page 3, the author describes a basic concept of the system:

As many FHE systems, we deal with noisy messages. In our case, the high bits of each block are used to hold significant bits, while the low bits contain noise. A fundamental identity that makes the system work is that given two bits x and y , we have: x + y = 2(x ∧ y) + (x ⊕ y). Thus, if we can add the values of two bits as integers, or even as integers modulo 4, we are simultaneously computing an AND and a XOR gate.

I don't understand the difference between "integers" and "integers modulo 4". If we have only two variables which hold a single bit, the sum of both can be a maximum of 2. So what is the necessity to use a modulo 4 ring? And why not modulo 3, modulo 8 or any other number?

• Welcome to Cryptography. As a beginner, you seem to start from the very high end of the Cryptography, even before taking a course about number theory. There is nothing special there. It is the usual half-adder. Module 4 is ok, but not 3. it must be power of 2. – kelalaka Nov 14 '19 at 13:31
• Thank you for your fast answer. I am taking a course in cryptography which is more advanced then I thought before. I know what a half-adder is and how it computes AND and XOR of the two bits x and y. But I still do not get why this modulo 4 thing, if my result is always between 0 and 2. – Martin1997 Nov 14 '19 at 13:38
• Mod 4 is two adder? – kelalaka Nov 14 '19 at 13:41

I think that Antoine Joux said modulo 4 just because he is explicitly working with two bits (the least significant for the xor and the most significant for the and), although that equation really holds over $$\mathbb{Z}$$ even if you reduce mod 3, as you noticed.

Indeed, in some point of the paper he even defines a function to extract a bit homomorphically.

Reducing modulo a larger integer (like mod 8) would also work, but it would be an overkill.

The whole point here is that if you can take two bits, operate them outside of $$\mathbb{Z}_2$$, and then extract the resulting bits independently, then you can perform a complete set of logical binary gates.

"Integers modulo 4" is usually the finite ring $$(\Bbb Z_4,+,*)$$ which internal laws are

+ | 0 1 2 3     * | 0 1 2 3
--+--------     --+--------
0 | 0 1 2 3     0 | 0 0 0 0
1 | 1 2 3 0     1 | 0 1 2 3
2 | 2 3 0 1     2 | 0 2 0 2
3 | 3 0 1 2     3 | 0 3 2 1


but here, the question's citation only deals with the finite group $$(\Bbb Z_4,+)$$.

difference between "integers" and "integers modulo 4"

In the later, everything is reduced to four values, which can be expressed on two bits, the two lower bits of normal integers.