# Efficient Implementation of PRESENT and GIFT on Quantum Computers
## 3 Proposed Method
### Quantum Circuit for GIFT Block Cipher
#### 3.2.1. Sbox of GIFT Block Cipher  
In [4], the author of GIFT block cipher presented two versions of Sbox. One is optimized for implementation in software and the other is optimized for implementation in hardware. Detailed processes are given in Algorithms 4 and 5 for software-oriented and hardware-oriented, respectively. Comparing these two Sboxes, the hardware-friendly Sbox offers more advantages over the software-friendly Sbox when it comes to quantum circuits. ```
0: 4-bit input \(x(x_{3},x_{2},x_{1},x_{0})\) (before entering Sbox). 0: 4-bit output \(x(x_{3},x_{2},x_{1},x_{0})\) (after performing Sbox). 1: \(x_{1}\gets x_{1}\) XOR (\(x_{0}\) AND \(x_{2}\))
2: \(\mathrm{t}\gets x_{0}\) XOR (\(x_{1}\) AND \(x_{3}\))
3: \(x_{2}\gets x_{2}\) XOR (\(\mathrm{t}\) OR \(x_{1}\))
4: \(x_{0}\gets x_{3}\) XOR \(x_{2}\)
5: \(x_{1}\gets x_{1}\) XOR \(x_{3}\)
6: \(x_{0}\leftarrow\) NOT \(x_{0}\)
7: \(x_{2}\gets x_{2}\) XOR (\(\mathrm{t}\) AND \(x_{1}\))
8: \(x_{3}\leftarrow\) t
9:return\(x(x_{3},x_{2},x_{1},x_{0})\)
```  
**Algorithm 4** Software-oriented implementation of GIFT Sbox  
In the software-friendly Sbox operation (see Algorithm 4), the input and output of operations are different (e.g., \(x_{0}=x_{3}\) XOR \(x_{2}\)). Qubits in quantum computers must be initialized to zero to overwrite the new value. In order to initialize a qubit to zero, the same value must exist in another qubit. The Algorithm 4 is designed as a quantum circuit Since the new value cannot be overwritten (e.g., \(x_{0}\gets x_{3}\) XOR \(x_{2}\), we have to allocate a new qubit and also allocate an additional qubit for temporary storage. On the other hand, we can see that in the hardware-oriented Sbox design of Algorithm 5, the input and output of the operation are always the same. ```
0: 4-bit input \(x(x_{3},x_{2},x_{1},x_{0})\) (before entering Sbox). 0: 4-bit output \(x(x_{3},x_{2},x_{1},x_{0})\) (after performing Sbox). 1: \(x_{1}\gets x_{1}\) XNOR (\(x_{0}\) NAND \(x_{2}\))
2: \(x_{0}\gets x_{0}\) XNOR (\(x_{1}\) NAND \(x_{3}\))
3: \(x_{2}\gets x_{2}\) XNOR (\(x_{0}\) NOR \(x_{1}\))
4: \(x_{3}\gets x_{3}\) XNOR \(x_{2}\)
5: \(x_{1}\gets x_{1}\) XNOR \(x_{3}\)
6: \(x_{2}\gets x_{2}\) XNOR (\(x_{0}\) NAND \(x_{1}\))
7:return\(x(x_{0},x_{2},x_{1},x_{3})\)
```  
**Algorithm 5** Hardware-oriented implementation of GIFT Sbox  
Therefore, we were able to optimize the quantum circuit by choosing a hardware-friendly Sbox. The resulting value can be stored in qubits that are entered into the operation. For example, the quantum circuit for line 4 of Algorithm 5 corresponds to lines 9 and 10 of Algorithm 6. The operation continues on \(x_{3}\) without allocating additional qubits. Therefore, no additional qubits are used and an optimized 4-qubit Sbox quantum circuit can be implemented. The implementation of GIFT Sbox quantum circuit is described in Algorithm 6. ```
0: 4-bit output \(x(x_{3},x_{2},x_{1},x_{0})\) (after performing Sbox). 1: \(x_{1}\gets x_{1}\) XOR (\(x_{0}\) NAND \(x_{2}\))
2: \(x_{0}\gets x_{0}\) XOR (\(x_{1}\) NAND \(x_{3}\))
3: \(x_{2}\gets x_{2}\) XOR (\(x_{0}\) NOR \(x_{1}\))
4: \(x_{3}\gets x_{3}\) XOR \(x_{2}\)
5: \(x_{1}\gets x_{1}\) XOR \(x_{3}\)
6: \(x_{2}\gets x_{2}\) XOR (\(x_{0}\) NAND \(x_{1}\))
7:return\(x(x_{0},x_{2},x_{1},x_{3})\)
```  
**Algorithm 6** Hardware-oriented implementation of GIFT Sbox  
The NOT operation is performed twice on lines 1, 2, 3 and 6 of the Algorithm 5. Two NOT operations cancel each other. The arrangement of input and output qubits is altered in Algorithm 6. It can be performed with one Swap gate on \(x_{0}\), \(x_{3}\). As mentioned earlier, Swap gates are not considered quantum resources. Quantum circuit for Sbox of GIFT block cipher is described in Figure 10.  
```
0: 4-qubit input \(x(x_{3},x_{2},x_{1},x_{0})\) (before entering Sbox). 0: 4-qubit output \(x(x_{3},x_{2},x_{1},x_{0})\) (after performing Sbox).