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?

  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    Nov 14 '19 at 13:31
  • $\begingroup$ 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. $\endgroup$
    – Martin1997
    Nov 14 '19 at 13:38
  • $\begingroup$ Mod 4 is two adder? $\endgroup$
    – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.