# On Non-Completeness and G-Equivariance
## 4 Non-Completeness Implies G-Equivariance
That is, when the output of \(g\) changes from \(0\) to \(1\), it is assumed that \(g\) consumes the energy \(e_{01}\), while \(g\) is assumed to consume the energy \(e_{10}\), ifchanges its output from 1 to 0. And, when the output bit of \(g\) is fixed at 0 or 1, \(g\) is assumed to consume the energy \(e_{00}\) or \(e_{11}\), respectively. Also, in the definition, \(\phi\in Map(n)\) was introduced to describe the arrival order of the gate's input signal. Thus, for example, \(\phi(j)=i\) in (8) implies that the \(j\)-th input signal \(a_{j}\) arrives at the \(i\)-th order. Since we are primarily interested in masking a 2-input AND gate, all the gates in the subsequent are assumed to have 2 inputs. Definition 2 ([14; 16]): For a positive integer \(d\) and any input \((a,\ b)\in\mathit{GF}(2^{2})\) of a gate \(g:\mathit{GF}(2^{2})\to\mathit{GF}(2)\), the tuple \((a^{0},a^{1},\ldots,a^{d},b^{0},b^{1},\ldots,\ b^{d})\in\mathit{GF}(2^{2(d+1)})\) is called a \(d\)-th order masked signal of \((a,\ b)\) if  
(1) \(a=a^{0}\oplus a^{1}\oplus\cdots\oplus a^{d}\) and \(b=b^{0}\oplus b^{1}\oplus\cdots\oplus b^{d}\)  
(2) \(\Pr(a^{i}=1)=\Pr(b^{i}=1)=\frac{1}{2}\) for any \(i,\ j=0,1,\ldots,d\)  
(3) For any \(i,\ j=0,1,\ \ldots,d,\ a^{i}\) and \(b^{i}\) are statistically independent, considered as random variables. Definition 3 ([14; 16]): A \(d\)-th order masked gate of a gate \(g:\mathit{GF}(2^{2})\to\mathit{GF}(2)\) is the tuple \((g^{0},g^{1},\ \ldots,g^{d})\) satisfying the following:  
(1) \(g^{0},g^{1},\ \ldots,g^{d}:\ \mathit{GF}(2^{2(d+1)})\to\mathit{GF}(2)\)  
(2) For any input \((a,\ b)\in\mathit{GF}(2^{2})\) of \(g\) and any \(d\)-th order masked signal \((a^{0},a^{1},\ldots,a^{d},b^{0},b^{1},\ldots,\ b^{d})\in\mathit{GF}(2^{2(d+1)})\) of \((a,\ b)\), we have \(g^{0}(\overline{a},\ \overline{b})\oplus g^{1}(\overline{a},\ \overline{b})\oplus\cdots\oplus g^{d}( \overline{a},\ \overline{b})=g(a,\ b)\) for \((\overline{a},\overline{b})=(a^{0},a^{1},\ldots,a^{d},b^{0},b^{1},\ldots,\ b^{d})\). In this case, each \(g^{k}\) of the \(d\)-th order masked gate \((g^{0},g^{1},\ \ldots,g^{d})\) is called a \(d\)-th order component masked gate of \(g\). Definition 4 ([14; 16]): Given a \(d\)-th order masked gate \((g^{0},g^{1},\ \ldots,g^{d})\) of a gate \(g:\mathit{GF}(2^{2})\to\mathit{GF}(2)\), a \(d\)-th order component masked gate, say \(g^{k}:\ \mathit{GF}(2^{2(d+1)})\to\mathit{GF}(2)\) isid-th order \(G\)-equivariant if for any \(\phi\in Map(2(d+1))\) and \(i=0,1,\ \ldots,\ 2d+1\), the expectation value \(E(E_{g^{k},i}((\overline{a},\ \overline{b}),(\overline{x},\ \overline{y})),\ \phi))\) is independent of any choice of \(d\)-th order masked signals \((\overline{a},\ \overline{b})=(a^{0},a^{1},\ldots,a^{d},b^{0},b^{1},\ldots,\ b^{d})\) of \((a,\ b)\in\mathit{GF}(2^{2})\) and \((\overline{x},\overline{y})=(x^{0},x^{1},\ \ldots,x^{d},y^{0},y^{1},\ldots,y^{d})\in \mathit{GF}(2^{2})\) of \((x,y)\in\mathit{GF}(2^{2})\). In the sequel, a \(d\)-th order G-equivariant component masked gate is briefly called as a G-equivariant gate, if there is no confusion. Lemma 1 ([14; 16]): Given a \(d\)-th order masked gate \((g^{0},g^{1},\ \ldots,g^{d})\) of a gate \(g:\mathit{GF}(2^{2})\to\mathit{GF}(2)\), a \(d\)-th order component masked gate, say \(g^{k}:\ \mathit{GF}(2^{2(d+1)})\to\mathit{GF}(2)\) is \(d\)-th order \(G\)-equivariant if and only if, for any \(\phi\in Map(2(d+1))\) and \(i=0,1,\ \ldots,\ 2d+1\), the following 16 values \(S(a,b,x,y)\) are equal for any choice \(a,b,x,y\in\{0,1\}\):  
\[S(a,b,x,y):= \sum_{ \begin{array}{c}a^{0},a^{1},\ldots,a^{d},b^{0},\ b^{1}, \ldots,b^{d},x^{0},x^{1},\ldots,x^{d},y^{0},y^{1},\ldots,\ y^{d}\\ a^{0}\oplus a^{1}\oplus\cdots\oplus a^{d}=a\\ b^{0}\oplus b^{1}\oplus\cdots\oplus b^{d}=b\\ x^{0}\oplus x^{1}\oplus\cdots\oplus x^{d}=x\\ y^{0}\oplus y^{1}\oplus\cdots\oplus y^{d}=y\end{array}