Why is XOR preferred over XNOR?

Question

The XOR operator seems to be a frequently used building block inside many cryptographic primitives. As far as I can see, its most desirable properties seem be that for the XOR of two bits $a\oplus b=c$:

1. The information is preserved. Either $a$ or $b$ can be recovered from $c$ and the other bit.
2. The information is hidden. An adversary can not learn anything about $a$ or $b$ from $c$ alone.

Neither AND nor OR has these properties but XNOR does. It seems like any cryptographic application using XOR could be constructed equivalently with XNOR, without incurring any loss in security. One possible reason to prefer XOR might be that XOR is equivalent to addition modulo 2, whereas XNOR would be addition plus 1 modulo 2, but this seems to be entirely mathematical, and I'm not sure if it actually results in any additional hardware complexity in practice.

Is the choice of XOR then an arbitrary one, made for historical reasons, or is there any tangible underlying motivation for using it over XNOR?

Answer 1

1. $\operatorname{XOR}$ is similar to addition when working on Booleans; by contrast, $\operatorname{XNOR}$ is not a group law if we want to use $0$ as neutral.
2. Economy for extension: we can build a 3-inputs $\operatorname{XOR}$ from two 2-inputs ones; we can't for $\operatorname{XNOR}$.
3. Economy for making one: we can build $\operatorname{XOR}$ with four identical 2-input $\operatorname{NAND}$, but that can't be done for $\operatorname{XNOR}$. The construction goes:
   • $z\gets(a\;\operatorname{NAND}\;b)$;
   • $x\gets (a\;\operatorname{NAND}\;z)$;
   • $y\gets(b\;\operatorname{NAND}\;z)$;
   • $c\gets (x\;\operatorname{NAND}\;y)=(a\;\operatorname{XOR}\;b)$.
     

Update: the later argument works only because/when $\operatorname{NAND}$ is cheaper, faster, or/and less power-hungry than $\operatorname{NOR}$. That indeed was the case in TTL logic: that source shows 4 NPN transistors for $\operatorname{NAND}$, including one with two emitters, versus 6 for $\operatorname{NOR}$. The same holds for RTL logic made from PNP transistors, which used to be popular when these where made using germanium. However, RTL logic using NPN transistors (typically, on a silicon Integrated Circuit), which favors $\operatorname{NOR}$, has also existed. Famously, the Appolo Guidance Computer was built from 3-inputs $\operatorname{NOR}$ gates, two per IC.

Answer 2

• Negations are harder to reason about.
• XNOR adds negation to XOR, one more step to consider.
• There is no advantage to XNOR as there is with NAND and NOR. Hardware NAND and NOR were the natural result of transistor logic way back to RTL.
• Hardware does generally not implement XNOR. (thx mb)

In light of the above there seems to be no argument for XNOR.

Multi-transistor RTL NOR gate

Answer 3

fgrieu's mathematical assumptions I believe to be correct, but the I have issues with everyone's hardware answers. When you make hardware, you are actually good at passing around $\mathbb{s}$ and $\bar{\mathbb{s}}$. I do not believe that it matters too much from the circuit side as I will give you whatever you want, and it's just a matter of the algorithm designer's preference from the cryptographic side. Also, considering modern CPUs, you are wasting so much power on fairyland items in software, a single transistors doesn't matter unless you are doing speciality things. When I do passively powered RFID ICs, I count every transistor, but when I make a processor, I really just am trying to get to tapeout.

There's a lot of XNORs in hardware. When I make circuits, I generally use mirror circuit architectures, which means that NAND, XNOR, etc, all take 8 transistors on aggressive nodes. Due to the mirror architecture, I get an inverted output, and you are forced into this architecture due to lithographic constraints. Attached is an image of the XNOR that was used on a 14nm implementation of the Simon Cipher.

The red are the polysilicon control lines over the green fins on a commercially available FinFet process at 14nm. The blues are my colored metal 1.

In summary, it's just up to the preference of the algorithm designer how they prefer things to be specified, but I'm going to make whatever works best for the logic.

Answer 4

You mention hardware complexity, but there definitely is more software complexity in using XNOR. Most programming languages have a XOR operator, but no XNOR. Likewise, assembly languages lack XNOR (at least x86 does). That means it would basically take twice the cycles to use XNOR in place of XOR, except where two XNORs would cancel and you'd be back to XOR.

Answer 5

As you mention, XOR corresponds to the addition in the Galois field GF(2). Therefore it seems to be a more natural choice than XNOR.

Both operations are so simple that there can hardly be a problem related to hardware complexity. Typical MOSFET implementations of XOR directly invert the input $A$ to $\neg A$, and then use $A$ and $\neg A$ in the rest of the circuit. A XOR can thus be transformed into an XNOR just by swapping the wires, without changing the number of transistors.