# On Non-Completeness and G-Equivariance
## 2 Prerequisite
### Masking Method  
Power attack, which was first introduced by [PERSON] et al. can retrieve sensitive information in cryptographic devices using devices' power consumption patterns ([2]). Various techniques were introduced as power attack countermeasures, among which the masking method is representative for securely implementing, for example, block ciphers against DPA(differential power attack).  
To apply the (Boolean) masking method to a function \(z=f(x):\mathrm{GF}(2^{n})\rightarrow\mathrm{GF}(2^{m})\), one should first determine the input masking order \(d_{in}\) and the output masking order \(d_{out}\) and then should take the following procedure: for given \(x\in\mathrm{GF}(2^{n})\),  
1. Randomly choose \(x^{1},\,\ldots,\,x^{d_{in}}\in\mathrm{GF}(2^{n})\).
2. Compute \(x^{0}=x\oplus x^{1}\oplus\cdots\oplus x^{d_{in}}\), where \(\oplus\) denotes the bitwise eXclusive-OR operation.
3. From \((x^{0},\,x^{1},\,\ldots,\,x^{d_{in}})\), compute \((z^{0},z^{1},\ldots,\,z^{d_{out}})\in\mathrm{GF}(2^{m})^{d_{out}+1}\) with \(z^{0}\oplus z^{1}\oplus\ldots\oplus z^{d_{out}}=f(x)\) in the manner that any information about the original input \(x\) is not leaked during the computation.  
The procedure above is usually called the \((d_{in},\,d_{out})\) -order masking scheme for \(z=f(x)\) and, if \(d_{in}=d_{out}=d\), it is also called the \(d\)-th order masking scheme. The vector \((x^{0},\,x^{1},\,\ldots,\,x^{d_{in}})\) is called the \(d_{in}\)-th order mask (or, sharing) of \(x\) or the \(d_{in}\)-th order input mask of \(z=f(x)\) and each \(x^{i}\) is called a share of \(x\). Similarly, \((z^{0},z^{1},\ldots,\,z^{d_{out}})\) is called the \(d_{out}\)-th order mask of \(z\) or the \(d_{out}\)-th order output mask of \(z=f(x)\), and each \(z^{i}\) is called a share of \(z\). Importantly, the quantities \(d_{in}\) and \(d_{out}\) are closely related to the effort an attacker has to pay to break the masking scheme. For example, to successfully recover a key from the masking scheme with \(d_{in}\)-th input order, it is believed that an attacker needs to observe at least \(d_{in}+1\) individual shares or statistical moments.  
The function computing the output mask \((z^{0},z^{1},\ldots,\,z^{d_{out}})\) given the input mask \((x^{0},\,x^{1},\,\ldots,\,x^{d_{in}})\) is denoted as \((f^{0},\,\,\ldots,\,f^{d_{out}})\) and is called a shared implementation of \(z=f(x)\), thus \(f^{i}(x^{0},\,\,x^{1},\,\ldots,\,x^{d_{in}})=z^{i}\) for each \(i\).  
Devising a masking scheme for linear or affine functions is known to be an easy task. For example, if \(z=f(x)\) is linear (with respect to \(\oplus\)) and \(x=x^{0}\oplus x^{1}\oplus\cdots\oplus x^{d_{in}}\), then \(f(x)=f(x^{0}\oplus x^{1}\oplus\cdots\oplus x^{d_{in}})=f(x^{0})\oplus\cdots \oplus f(x^{d_{in}})\), thus letting \(f^{i}(x^{0},\,\,x^{1},\,\ldots,\,x^{d_{in}})=f(x^{i})\) gives a well-established masking scheme for \(f\). However, designing a masking scheme for non-linear functions, such as block ciphers' S-box, is non-trivial, and the gate-level masking method was introduced to address this issue, especially in the hardware masking scheme design [15].  
The idea of the gate-level masking method is very simple: after decomposing any function (or circuit) into basic gates, like AND, XOR and so on, and individually applying an appropriate masking scheme to the corresponding basic gates, the resulting circuit will serve as the masking scheme for the original function. Especially, since AND, OR, NAND, and NOR gates are the only non-linear basic gates, and OR, NAND, and NOR gates can be constructed with the composition of AND, XOR, and NOT gates; the main research of the gate-level masking method focuses on how to apply the masking method to the AND gate. For example, Figure 1 shows the masking scheme for the 2-input AND gate proposed by [PERSON] [15], which can be mathematically described as: for a random bit \(r\),  
\[(x^{0},x^{1},\,y^{0},y^{1})\rightarrow(z^{0},z^{1})=(((((r\oplus x^{0}y^{0}) \oplus x^{1}y^{0})\oplus x^{0}y^{1})\oplus x^{1}y^{1},r). \tag{1}\]