# On Non-Completeness and G-Equivariance
## 3 Non-Completeness Implies 1 st-Order DPA Security? As stated in Section 2, Threshold Implementation is known to be provably secure against the 1 st-order differential power attack even in the presence of glitches, and it is usually referenced that the corresponding security proof is given in Theorem 2 and Corollary 1 of [11]. Unfortunately, as indicated below, the proof is not satisfactory in the sense that there is a counter-example of not being secure against the glitch attack while satisfying the condition presented in [11]. For easy reference, here, we re-state the theorem. **Theorem 1** (same with Theorem 2 in [11]). : _For a shared implementation \((f^{0},\ \ldots,\ f^{d_{out}})\) of \(z=f(x)\), if the input shares are uniform and \((f^{0},\ \ldots,\ f^{d_{out}})\) is correct and non-complete, then each output share \(z^{i}\) is statistically independent of the original input \(x\) and the original output \(z\). And, the same holds for any intermediate result that is appearing during the computation of \((f^{0},\ \ldots,\ f^{d_{out}})\) and for any physical quantities like power consumption, electro-magnetic radiation, etc., which are a function of these intermediate results._  
Note that the original theorem in [11] was stated for the multi-input and multi-output function, while Theorem 1 above assumes that \(f\) has a single input and single output. However, the difference does not affect the validity of the argument below. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \(z^{0}\oplus z^{1}\oplus z^{2}\) & \multicolumn{4}{c}{**0**} & \multicolumn{4}{c}{**1**} \\ \hline \((z^{0},z^{1},z^{2})\) & (0,0,0) & (0,1,1) & (1,0,1) & (1,0,0) & (1,0,0) & (0,1,0) & (1,1,1) \\ \hline
**Prob.** & 3/16 & 3/16 & 3/16 & 3/16 & 1/16 & 1/16 & 1/16 & 1/16 \\ \hline \end{tabular}
\end{table} 
Table 1: Probability distribution of \((z^{0},z^{1},z^{2})\) in (4). In [11], for proving the theorem above, the authors showed that, for any variable \(\tau\) appearing in the computation of \((f^{0},\ \ldots,\ f^{d_{out}})\) and any input \(x\) of \(f\),  
\[\Pr(\tau)=\Pr(\tau\big{\{}x\big{\}}). \tag{5}\]  
Clearly, the Equation (5) implies that \(\tau\) and \(x\) are statistically independent. And then, [11] presented the following corollary:  
**Corollary 1** ([11]). : _For a shared implementation \((f^{0},\ \ldots,\ f^{d_{out}})\) of \(z=f(x)\), if the input shares are uniform and \((f^{0},\ \ldots,\ f^{d_{out}})\) is correct and non-complete, then the expected value of the power consumption of a circuit implementing \((f^{0},\ \ldots,\ f^{d_{out}})\) is independent of \(x\) and \(z\), even in the presence of glitches or the delayed arrival of some inputs._  
Now, in proving the corollary above, the authors of [11] stated that \"Since the proof of Theorem 2 makes no assumption on the behavior of the circuit and/or the presence of glitches, the theorem holds for each sub-circuit computing one of the \(y_{i}^{j}\), also in the case of delayed inputs or glitches. Furthermore, the mean power consumption of the whole circuit is the sum of the mean power consumptions of the sub-circuits and expectation is a linear operation\" [11]. After all, [11] used the argument that, if all the intermediate variables of the shared circuit are statistically independent of the input and the output, the shared implementation is secure against the 1 st-order DPA even in the presence of a glitch. However, this argument is not true, in general. That is, there are some shared circuits whose intermediate variables are statistically independent of the input and the output, but that are not secure against the glitch attack.