# On Non-Completeness and G-Equivariance
## 4 Non-Completeness Implies G-Equivariance  
To solve the problem discussed in the previous section, we use the extended concept of the G-equivariance in [16]. Originally, the G-equivariance was introduced as a glitch attack countermeasure, and a gate (or a function) is defined to be G-equivariant if the energy consumption of the gate is independent of the arrival order of input signals [14]. However, as paper [14] indicated, there are no G-equivariant gates in which the Boolean sum is equal to the 2-input AND gate evaluation, and the authors loosened the condition imposed on the G-equivariance to get the semi-G-equivariance. The semi-G-equivariance (the exact definition of which can be found in [14]) requires the energy consumption of a gate to be independent of the order of input signals with the constraint that some signals should arrive at the gate simultaneously, and [14] proved that there are some semi-G-equivariant gates that summed up to give the 2-input AND gate. For example, the gates \(g^{0},g^{1}\) with  
\[g^{0}(x^{0},\ x^{1},y^{0},y^{1})=x^{0}\oplus y^{0} \tag{6}\]  
\[g^{1}(x^{0},\ x^{1},y^{0},y^{1})=x^{0}\oplus y^{0}\oplus x^{0}y^{0}\oplus x^{ 0}y^{1}\oplus x^{1}y^{0}\oplus x^{1}y^{1}\]  
have the property that they are semi-G-equivariant, that is, their energy consumption is independent of the arrival order of input signals if \(x^{0}\) and \(x^{1}\) arrive at \(g^{0}\) or \(g^{1}\) at the same time and \(y^{0}\) and \(y^{1}\) arrive at \(g^{0}\) or \(g^{1}\) simultaneously, and \(g^{0}(x^{0},\ x^{1},y^{0},y^{1})\oplus g^{1}(x^{0},\ x^{1},y^{0},y^{1})=(x^{0 }\oplus x^{1})(y^{0}\oplus y^{1})\). However, there is a critical problem with semi-G-equivariant gates. It is not easy to satisfy the condition imposed on the gates. That is, for example, it is very hard to make \(x^{0}\) and \(x^{1}\) (and \(y^{0}\) and \(y^{1}\) as well) in (6) arrive at \(g^{0}\) or \(g^{1}\) at the same time. The custom design process may solve the issue; however, with a high cost. The G-equivariance and semi-G-equivariance in [14] were basically defined in the 1 st-order setting. More precisely, any input signal \(x\) of a gate is assumed to be decomposed as \((x^{0},\ x^{1})\) with \(x=x^{0}\oplus x^{1}\). However, there is no justification for why the input signals for the G-equivariant gate should have such form. And, using the extended notion of G-equivariance to the higher-order setting in [16], this paper assumes that every signal \(x\) is represented as \((x^{0},\ x^{1},\ldots,\ x^{d})\) with \(x=x^{0}\oplus x^{1}\oplus\cdots\oplus x^{d}\) for a given positive integer \(d\). In the subsequent, a gate with \(n\) inputs and \(1\) output is considered as a Boolean function \(g:\ \mathrm{GF}(2^{n})\rightarrow\mathrm{GF}(2)\), where \(\mathrm{GF}(2)\) stands for the binary finite field with addition operation \(\oplus\), and \(\mathrm{GF}(2^{n})\) is an extension field of degree \(n\) over \(\mathrm{GF}(2)\), which can be considered as an \(n\)-dimensional vector space over \(\mathrm{GF}(2)\). For a positive integer \(n\), we denote \(Map(n)\) as the set of all mappings from the set \(\{0,\ \ldots,\ n-1\}\) into itself. **Definition 1** ([14;16]). : _Given a positive integer \(n\), a gate \(g:\ GF(2^{n})\to GF(2)\) and \(i=0,1,\ \ldots,\ n-1\), the partial energy function \(E_{g,i}\) is defined as_  
\[E_{g,i}:\mathrm{GF}(2^{n})\times\mathrm{GF}(2^{n})\times Map(n)\rightarrow\ V \tag{7}\]  
\[((a,x),\ \phi)\oplus e_{g(p)g(p+1}\ )\]  
_where \(V\) stands for the 4-dimensional real vector space with the basis \(\left\{e_{00},\ e_{01},\ e_{10},\ e_{11}\right\}\) and, for \(a=(a_{0},\ \ldots,\ a_{n-1})\), \(x=(x_{0},\ \ldots,\ x_{n-1})\) and \(\phi\in Map(n)\), \(b^{i}=(b^{i}_{0^{\prime}},\ \ldots,\ b^{i}_{n-1})\ \in\ GF(2^{n})\) in (7) is defined by: \(b^{i+1}=\ \begin{cases}x_{j}&if\ \phi(j)=i\\ b^{i}_{j}&\text{otherwise}\end{cases} \)._  
In Definition 1, the basis vectors \(e_{00},\ e_{01},\ e_{10},\ e_{11}\) of \(V\) can actually be interpreted as the amount of power consumed while \(g\) changes or holds its output.