11
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • $\begingroup$ I think the reason is, the XNOR gate is not considered on any abstraction level beyond the transistor level. Especially from an algebraic point of view: We can use equations. There is no need for a gate which represents "if A = B, output 1, else 0". And if there is, we just use "A+B+1" $\endgroup$ – tylo May 19 '14 at 9:51
  • $\begingroup$ It you are interested in Boolean logic check out De Morgan's laws, they are good for reversing logical operations and are applicable to computer code. $\endgroup$ – zaph Mar 26 '18 at 22:14
10
$\begingroup$
  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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks.. This explains everything.. (sorry for the delayed response). So, do these reason still hold at present, or if is XOR still being preferred for historic reasons (ones you mentioned). If we were to redo the whole things again at this present point of time, will we still choose XOR? $\endgroup$ – Haris Apr 6 '18 at 10:04
  • 1
    $\begingroup$ @Haris: I believe that 1 is the major, technology-independent reason why XOR was, is and should be preferred to XNOR. Reason 2 is a consequence. Reason 3 is dubious, and very technology-dependent. $\endgroup$ – fgrieu♦ Apr 6 '18 at 10:22
5
$\begingroup$
  • 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
Multi-transistor RTL NOR gate

| improve this answer | |
$\endgroup$
  • $\begingroup$ In your 3rd point, you mean that constructing XOR with NAND and NOR is easier, as compared to constructing XNOR? $\endgroup$ – Haris Mar 26 '18 at 19:23
  • $\begingroup$ Missing: processors do generally not implement XNOR and there is no advantage over XOR... $\endgroup$ – Maarten Bodewes♦ Mar 26 '18 at 21:28
  • $\begingroup$ By hardware I am going back to ~1960 and RTL where there was a pull doe transistor and a resistor. For a NOR if either input went high a transistor conducted and pulled down the output, a natural NOR. See Multi-transistor RTL NOR gate. Sadly I was designing circuits with these and this is the logic that flew to the Moon on Apollo. $\endgroup$ – zaph Mar 26 '18 at 22:12
5
$\begingroup$

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.

enter image description here

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ How XOR historically became preferred to XNOR is relevant to the question. FET (much more, 14nm) was unknown then. $\endgroup$ – fgrieu♦ Mar 27 '18 at 14:18
  • $\begingroup$ @fgrieu I agree, but if the history would have been true there would have been ECL logic and not TTL, as the first ICs that did cryptographic primitives were ECL. I tried to make it clear that the hardware doesn't really matter, and then showed how we do it now. $\endgroup$ – b degnan Mar 27 '18 at 14:28
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ ARMv8 has EON instruction. SPARC has XNOR instruction. Then again, few other processors have it. $\endgroup$ – user4982 May 19 '14 at 16:10
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ But XNOR is just equality, which seems like a more primitive notion... $\endgroup$ – user76284 Jul 7 '18 at 3:26

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