# On Non-Completeness and G-Equivariance
## 4 Non-Completeness Implies G-Equivariance
} \tag{12}\] \[a^{0}\oplus a^{1}\oplus a^{2}=a\] \[b^{0}\oplus b^{1}\oplus b^{2}=b\] \[x^{0}\oplus x^{1}\oplus x^{2}=x\] \[y^{0}\oplus y^{1}\oplus y^{2}=y\]  
for \(\Delta a=a\oplus a^{\prime}\), \(\Delta b=b\oplus b^{\prime}\), \(\Delta x=x\oplus x^{\prime}\), \(\Delta y=y\oplus y^{\prime}\), \(\overline{a}^{0}=a^{0}\oplus\Delta a\), \(\overline{b}^{0}=b^{0}\oplus b\), \(\overline{x}^{0}=x^{0}\oplus\Delta x\), \(\overline{y}^{0}=y^{0}\oplus\Delta y\), \((\overline{a}^{\prime},\overline{b}^{\prime})=(\overline{a}^{0}\), \(a^{1},a^{2},\overline{b}^{0}\), \(b^{1},b^{2})\) and \((\overline{x}^{\prime},\overline{y}^{\prime})=(\overline{x}^{0}\), \(x^{1},x^{2}\), \(\overline{y}^{0}\), \(y^{1}\), \(y^{2})\) since \(g^{k}(x_{0},\ x_{1},\ x_{2},\ y_{0},\ y_{1},\ y_{2})\) is independent of \(x_{0}\) and \(y_{0}\), thus changing \(a^{0}\) and \(b^{0}\) to \(\overline{a}^{0}\) and \(\overline{b}^{0}\) in \((\overline{a},\ \overline{b})=(a^{0},a^{1},a^{2},b^{0},b^{1},\ b^{2})\) and changing \(x^{0}\) and \(y^{0}\) to \(\overline{x}^{0}\) and \(\overline{y}^{0}\) in \((\overline{x},\ \overline{y})=(x^{0},\underline{x}^{1},x^{2},y^{0},y^{1},y^{2})\) does not impact on evaluating \(g^{k}\) and \(E_{g^{k},i}\). Finally, substituting \(a^{0}\) with \(\overline{a}^{0}\oplus\Delta a\), \(b^{0}\) with \(\overline{b}^{0}\oplus\Delta b\), \(x^{0}\) with \(\overline{x}^{0}\oplus\Delta x\) and \(y^{0}\) with \(\overline{y}^{0}\oplus\Delta y\), the Equation (12) is equal to  
\[\sum\ a^{1},a^{2},\ b^{1},b^{2},x^{1},x^{2},y^{1},\ y^{2}\ \ \sum\
olimits_{ \overline{awhich is again equal to  
\[S(a^{\prime},b^{\prime},x^{\prime},y^{\prime})= \tag{14}\] \[\overline{a}^{0},a^{1},a^{2},\overline{b}^{0},\ b^{1},b^{2}, \overline{x}^{0},x^{1},x^{2},\overline{y}^{0},y^{1},\ y^{2}\] \[\overline{a}^{0}\oplus a^{1}\oplus a^{2}=a^{\prime}\] \[\overline{b}^{0}\oplus b^{1}\oplus b^{2}=b^{\prime}\] \[\overline{x}^{0}\oplus x^{1}\oplus x^{2}=x^{\prime}\] \[\overline{y}^{0}\oplus y^{1}\oplus y^{2}=y^{\prime}\]  
And, this completes the proof. **Corollary 2**. : _The following 2 nd-order component masked gates \(f^{0},f^{1},f^{2}:\mathrm{GF}(2^{6})\to\mathrm{GF}(2)\) give the shared implementation \((f^{0},f^{1},f^{2})\) of the 2-input AND gate whose energy consumption is independent of the arrival order of input signals:_  
\[b^{0}\oplus b^{1}\oplus b^{2}=b\]0 \[b^{0}\oplus b^{1}\oplus b^{2}=b\]1 \[b^{0}\oplus b^{1}\oplus b^{2}=b\]2  
_In other words, the energy consumption of \(f^{0},f^{1},f^{2}\) in (15) is independent of the arrival order of input signals and \(f^{0}(x^{0},\ x^{1},x^{2},y^{0},y^{1},y^{2})\oplus f^{1}(x^{0},\ x^{1},x^{2},y ^{0},y^{1},y^{2})\oplus f^{2}(x^{0},\ x^{1},x^{2},y^{0},y^{1},y^{2})=(x^{0} \oplus x^{1}\oplus x^{2})(y^{0}\oplus y^{1}\oplus y^{2})\)._  
Proof. : The claim is a direct consequence of Theorem 2 since \(f^{0},f^{1},f^{2}\) are first-order non-complete. By Corollary 2, the set of first-order non-complete gates is a subset of the set of 2 nd-order G-equivariant gates. And, at this point, it may be questionable if there are any 2 nd-order G-equivariant but first-order complete gates that can be used for implementing the AND gate in a shared form. Interestingly, the answer is yes. For example, it can be shown that the following gates \(g^{0},g^{1},g^{2}\) are G-equivariant:  
\[b^{0}\oplus b^{1}\oplus b^{2}=b\]3  
\[b^{0}\oplus b^{1}\oplus b^{2}=b\]4 \[b^{0}\oplus b^{1}\oplus b^{2}=b\]5  
Also, the XOR sum of \(g^{0},g^{1},g^{2}\) in (16) gives the AND gate evaluation for the original inputs, that is, \(g^{0}(x^{0},\ x^{1},x^{2},y^{0},y^{1},y^{2})\oplus g^{1}(x^{0},\ x^{1},x^{2},y ^{0},y^{1},y^{2})\oplus g^{2}(x^{0},\ x^{1},x^{2},y^{0},y^{1},y^{2})\) is equal to \((x^{0}\oplus x^{1}\oplus x^{2})(y^{0}\oplus y^{1}\oplus y^{2})\). However, since \(g^{0}\) involves all shares \(x^{0},x^{1},x^{2}\) of \(x\) for its computation, it is not non-complete. **Remark 2**. : _The G-equivariant gate is for ensuring the security only for the single gate; thus, it does not guarantee the security of the composition of several gates.