# On Non-Completeness and G-Equivariance
## 2 Prerequisite
### Glitch Attack and Countermeasures  
Most of the previous gate level masking methods prior to the glitch attack implicitly or explicitly assumed that all input signals of any gate arrive at the gate simultaneously. However, the idealized assumption is shown not to hold in practice. That is, due to the gate delay and the variable path lengths, which are very common in the semiconductor technology, each input signal arrives at the gate at different times. Moreover, eliminating such the arrival time variation is known to be a hard task, especially for CMOS, the most widely used semiconductor technology. And, when input signals get to a gate at a different time, the state of the gate's output signal fluctuates within a clock cycle until it is finally stabilized at a certain value. This phenomenon is called the glitch or the hazard. The glitch phenomenon highly affects the amount of electrical power consumed by circuits. Moreover, the amount of consumed power is highly related to the circuit's input. And, the power analysis attack which analyzes the relationship between the glitch phenomenon and the power consumption pattern is called the glitch attack [7; 8; 9]. Unfortunately, many gate-level masking schemes are known to be vulnerable to the glitch attack. Various countermeasures have been proposed since the glitch attack was introduced, and this paper focuses on the G-equivariant gates [14] and the threshold implementation [10; 11; 12; 13]. The notion of G-equivariant gates relies on the belief that if a (averaged) toggling count of the gate's output is constant regardless of the arrival order of the gate input signals [14], the gate's power consumption pattern will not be influenced by the glitch phenomenon so that the glitch attack can be prevented. Unfortunately, as noted in [14], there are no 2-share G-equivariant gates in which the XOR sum gives rise to the AND-gate evaluation of the original input values. More precisely, there are no G-equivariant gates \(g^{0}\), \(g^{1}:\,\mathrm{GF}(2)^{4}\rightarrow\mathrm{GF}(2)\) satisfying  
\[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}). \tag{2}\]  
To remedy this undesirable situation, the authors introduced the concept of semi-G-equivariance with the weakened condition that, in the Equation (2), \(x^{0},x^{1}\) arrives at the gate at the same time and \(y^{0},y^{1}\) arrives at the gate simultaneously. However, even though there are some semi-G-equivariant gates that are available for glitch-attack-resistantly constructing the AND gate, there have been some doubts about the appropriateness of such weakened conditions. TI (Threshold Implementation, [10; 11; 12; 13]) was proposed as another glitch attack countermeasure and is said to be provably secure even in the presence of glitches. TI is defined to be a masking scheme  
Figure 1: Masked AND gate by [PERSON]. satisfying three specific properties: correctness, non-completeness, and uniformness. Given a function \(z=f(x)\), the shared implementation \((f^{0},\ \ldots,\ f^{d_{out}})\) of \(f\) is said to be correct if  
\[f^{0}(x^{0},\ x^{1},\ \ldots,\ x^{d_{in}})\oplus\cdots\oplus f^{d_{out}}(x^{0}, \ x^{1},\ \ldots,\ x^{d_{in}})=f(x^{0}\oplus x^{1}\oplus\cdots\oplus x^{d_{in}})\]  
for any mask \((x^{0},\ x^{1},\ \ldots,\ x^{d_{in}})\) of \(x\). And \((f^{0},\ \ldots,\ f^{d_{out}})\) is defined to be \(d\)-th order non-complete if any processing of up to \(d\) component functions \(f^{i}\) does not require at least one input share.