XOR gate | EPFL Graph Search

XOR gate (sometimes EOR, or EXOR and pronounced as Exclusive OR) is a digital logic gate that gives a true (1 or HIGH) output when the number of true inputs is odd. An XOR gate implements an exclusive or (\nleftrightarrow) from mathematical logic; that is, a true output results if one, and only one, of the inputs to the gate is true. If both inputs are false (0/LOW) or both are true, a false output results. XOR represents the inequality function, i.e., the output is true if the inputs are not alike otherwise the output is false. A way to remember XOR is "must have one or the other but not both". An XOR gate may serve as a "programmable inverter" in which one input determines whether to invert the other input, or to simply pass it along with no change. Hence it functions as a inverter (a NOT gate) which may be activated or deactivated by a switch. XOR can also be viewed as addition modulo 2. As a result, XOR gates are used to implement binary addition in computers. A

More Results on Shortest Linear Programs

Subhadeep Banik

At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates required to completely describe a linear system of equations. In the above paper the authors showed that the commonly used metrics like d-xor/s-xor count that are used to judge the ``lightweightedness'' do not represent the minimum number of xor gates required to describe a given MDS matrix. In fact they used heuristic based algorithms of Boyar/Peralta and Paar to find implementations of MDS matrices with even fewer xor gates than was previously known. They proved that the AES mixcolumn matrix can be implemented with as little as 97 xor gates. In this paper we show that the values reported in the above paper are not optimal. By suitably including random bits in the instances of the above algorithms we can achieve implementations of almost all matrices with lesser number of gates than were reported in the above paper. As a result we report an implementation of the AES mixcolumn matrix that uses only 95 xor gates. In the second part of the paper, we observe that most standard cell libraries contain both 2 and 3-input xor gates, with the silicon area of the 3-input xor gate being smaller than the sum of the areas of two 2-input xor gates. Hence when linear circuits are synthesized by logic compilers (with specific instructions to optimize for area), most of them would return a solution circuit containing both 2 and 3-input xor gates. Thus from a practical point of view, reducing circuit size in presence of these gates is no longer equivalent to solving the shortest linear program. In this paper we show that by adopting a graph based heuristic it is possible to convert a circuit constructed with 2-input xor gates to another functionally equivalent circuit that utilizes both 2 and 3-input xor gates and occupies less hardware area. As a result we obtain more lightweight implementations of all the matrices listed in the ToSC paper.

2019

Further Results on Efficient Implementations of Block Cipher Linear Layers

Subhadeep Banik

At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates required to completely describe a linear system of equations. In the above paper the authors showed that the commonly used metrics like d-xor/s-xor count that are used to judge the “lightweightedness” do not represent the minimum number of xor gates required to describe a given MDS matrix. In fact they used heuristic based algorithms of Boyar-Peralta and Paar to find implementations of MDS matrices with even fewer xor gates than was previously known. They proved that the AES mixcolumn matrix can be implemented with as little as 97 xor gates. In this paper we show that the values reported in the above paper are not optimal. By suitably including random bits in the instances of the above algorithms we can achieve implementations of almost all matrices with lesser number of gates than were reported in the above paper. As a result we report an implementation of the AES mixcolumn matrix that uses only 95 xor gates. In FSE conference of ToSC 2019, Li et al. had tweaked the Boyar-Peralta algorithm to get low depth implementations of many matrices. We show that by introducing randomness in the tweaked algorithm, it is again possible to get low depth implementations with lesser number of gates than the above paper. As a result, we report a depth implementation of the AES mixcolumn matrix that uses only 103 xor gates, which is 2 gates less than the previous implementation. In the second part of the paper, we observe that most standard cell libraries contain both 2 and 3-input xor gates, with the silicon area of the 3-input xor gate being smaller than the sum of the areas of two 2-input xor gates. Hence when linear circuits are synthesized by logic compilers (with specific instructions to optimize for area), most of them would return a solution circuit containing both 2 and 3-input xor gates. Thus from a practical point of view, reducing circuit size in presence of these gates is no longer equivalent to solving the shortest linear program. In this paper we show that by adopting a graph based heuristic it is possible to convert a circuit constructed with 2-input xor gates to another functionally equivalent circuit that utilizes both 2 and 3-input xor gates and occupies less hardware area. As a result we obtain more lightweight implementations of all the matrices listed in the ToSC paper.

2021

Top-Down Fabrication of Gate-All-Around Vertically-Stacked Silicon Nanowire FETs with Controllable Polarity

Michele De Marchi, Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Yusuf Leblebici, Davide Sacchetto, Jian Zhang

Asthe currentMOSFET scaling trend is facing strong limitations, technologies exploiting novel degrees of freedom at physical and architecture level are promising candidates to enable the continuation of Moore's predictions. In this paper, we report on the fabrication of novel ambipolar Silicon nanowire (SiNW) Schottky-barrier (SB) FET transistors featuring two independent gate-all-around electrodes and vertically stacked SiNW channels. A top-down approach was employed for the nanowire fabrication, using an e-beam lithography defined design pattern. In these transistors, one gate electrode enables the dynamic configuration of the device polarity (n- or p-type) by electrostatic doping of the channel in proximity of the source and drain SBs. The other gate electrode, acting on the center region of the channel switches ON or OFF the device. Measurement results on silicon show I-on/I-off > 10(6) and subthreshold slopes approaching the thermal limit, SS approximate to 64 mV/dec (70 mV/dec) for p(n)-type operation in the same physical device. Finally, we show that the XOR logic operation is embedded in the device characteristic, and we demonstrate for the first time a fully functional two-transistor XOR gate.

Institute of Electrical and Electronics Engineers2014

Further Results on Efficient Implementations of Block Cipher Linear Layers

Subhadeep Banik

At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates required to completely describe a linear system of equations. In the above paper the authors showed that the commonly used metrics like d-xor/s-xor count that are used to judge the “lightweightedness” do not represent the minimum number of xor gates required to describe a given MDS matrix. In fact they used heuristic based algorithms of Boyar-Peralta and Paar to find implementations of MDS matrices with even fewer xor gates than was previously known. They proved that the AES mixcolumn matrix can be implemented with as little as 97 xor gates. In this paper we show that the values reported in the above paper are not optimal. By suitably including random bits in the instances of the above algorithms we can achieve implementations of almost all matrices with lesser number of gates than were reported in the above paper. As a result we report an implementation of the AES mixcolumn matrix that uses only 95 xor gates. In FSE conference of ToSC 2019, Li et al. had tweaked the Boyar-Peralta algorithm to get low depth implementations of many matrices. We show that by introducing randomness in the tweaked algorithm, it is again possible to get low depth implementations with lesser number of gates than the above paper. As a result, we report a depth implementation of the AES mixcolumn matrix that uses only 103 xor gates, which is 2 gates less than the previous implementation. In the second part of the paper, we observe that most standard cell libraries contain both 2 and 3-input xor gates, with the silicon area of the 3-input xor gate being smaller than the sum of the areas of two 2-input xor gates. Hence when linear circuits are synthesized by logic compilers (with specific instructions to optimize for area), most of them would return a solution circuit containing both 2 and 3-input xor gates. Thus from a practical point of view, reducing circuit size in presence of these gates is no longer equivalent to solving the shortest linear program. In this paper we show that by adopting a graph based heuristic it is possible to convert a circuit constructed with 2-input xor gates to another functionally equivalent circuit that utilizes both 2 and 3-input xor gates and occupies less hardware area. As a result we obtain more lightweight implementations of all the matrices listed in the ToSC paper.

2021

More Results on Shortest Linear Programs

Subhadeep Banik

2019