# Efficient Implementation of PRESENT and GIFT on Quantum Computers
## 3 Proposed Method
### Quantum Circuit for PRESENT Block Cipher
#### 3.1.2.  
Classical computers can utilize a predefined Sbox that directly matches the output value according to the input value(i.e., Table 1). However, the predefined Sbox cannot be used in quantum computers where multiple values exist as probabilities due to the qubit superposition. For quantum computers, we have to implement the Sbox equation as a quantum circuit with different outputs depending on the input. The Sbox operation of PRESENT block cipher is shown in Equation (10). The notation \(x_{0}x_{1}x_{2}^{\prime}\) indicates \(x_{0}\) AND \(x_{1}\) AND (NOT \(x_{2}\)).  
To implement this in a quantum circuit, additional qubits and expensive quantum gates should be used. An additional 4 qubits must be allocated to store the result value of Sbox (i.e., \(\text{Sbox}(x_{0})\), \(\text{Sbox}(x_{1})\), \(\text{Sbox}(x_{2})\), and \(\text{Sbox}(x_{3})\)) and many AND operations in Equation (10) increase the use of Toffoli gate, which is expensive quantum gates.  
\[\begin{array}{l}\text{Sbox}(x_{0})\leftarrow x_{3}^{\prime}x_{2}^{\prime}x_{0}\oplus x_{3}^{ \prime}x_{1}x_{0}\oplus x_{3}x_{2}^{\prime}x_{0}\oplus x_{3}x_{1}x_{0}^{\prime }\oplus x_{3}x_{2}x_{1}^{\prime}x_{0}\oplus x_{3}^{\prime}x_{2}x_{1}^{\prime }x_{0}^{\prime}\\ \text{Sbox}(x_{1})\leftarrow x_{3}^{\prime}x_{2}^{\prime}x_{1}\oplus x_{3}x_{2}x_{ 0}\oplus x_{3}^{\prime}x_{1}x_{0}^{\prime}\oplus x_{3}x_{2}^{\prime}x_{1}^{ \prime}\oplus x_{3}x_{2}^{\prime}x_{0}^{\prime}\\ \text{Sbox}(x_{2})\leftarrow x_{3}x_{2}x_{1}^{\prime}\oplus x_{2}^{\prime}x_{1}x_ {0}^{\prime}\oplus x_{3}^{\prime}x_{2}x_{1}x_{0}\oplus x_{3}^{\prime}x_{2}^{ \prime}x_{1}^{\prime}\oplus x_{2}^{\prime}x_{1}^{\prime}x_{0}\\ \text{Sbox}(x_{3})\leftarrow x_{3}x_{2}^{\prime}x_{1}\oplus x_{3}x_{2}^{\prime}x_ {0}\oplus x_{3}^{\prime}x_{1}^{\prime}x_{0}^{\prime}\oplus x_{3}^{\prime}x_{ 2}x_{1}\oplus x_{3}^{\prime}x_{1}x_{0}\\ \end{array} \tag{10}\]  
In order to avoid such an inefficient Sbox implementation of Equation (10), we implemented the optimal Sbox quantum circuit using the LIGHTER-R tool. The LIGHTER-R tool generates quantum circuits using graph-based MITM search algorithm according to the input and output values. Input qubits of the quantum circuit are used as the output qubits after the Sbox operation is completed. Therefore, there is no need to allocate additional qubits, and the graph-based MITM search algorithm matches output values more simply than the Equation (10). By using the LIGHTER-R tool, we can implement an optimized PRESENT Sbox quantum circuit with no additional qubits and low gate cost. The optimized implementation of PRESENT Sbox quantum circuit using the LIGHTER-R is shown in Algorithm 2.  
```
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).
1: \(x_{1}\leftarrow\) CNOT \((x_{2},x_{1})\)
2: \(x_{3}\leftarrow\) Toffoli \((x_{1},x_{2},x_{3})\)
3: \(x_{2}\leftarrow\) Toffoli \((x_{3},x_{1},x_{2})\)
4: \(x_{1}\leftarrow\) Toffoli \((x_{0},x_{2},x_{1})\)
5: \(x_{2}\leftarrow\) CNOT \((x_{3},x_{2})\)
6: \(x_{3}\leftarrow\) X \((x_{3})\)
7: \(x_{2}\leftarrow\) CNOT \((x_{1},x_{2})\)
8: \(x_{0}\leftarrow\) CNOT \((x_{3},x_{0})\)
9: \(x_{1}\leftarrow\) CNOT \((x_{0},x_{1})\)
10: \(x_{0}\leftarrow\) X \((x_{0})\)
11: \(x_{3}\leftarrow\) Toffoli \((x_{1},x_{2},x_{3})\)
12:return\(x(x_{1},x_{3},x_{2},x_{0})\)
```  
**Algorithm 2** Quantum circuit using LIGHTER-R for Sbox of PRESENT block cipher The arrangement of input qubits and output qubits was changed in Algorithm 2. It can be performed with Swap gates on \(x_{1}\), \(x_{3}\) and \(x_{1}\), \(x_{2}\). However, this can be done by qubit relabeling to treat \(x_{1}\) as \(x_{2}\), \(x_{2}\) as \(x_{3}\), and \(x_{3}\) as \(x_{1}\) without Swap gates. Swap gates are used in the implementation, but not counted as resources. Figure 9 shows PRESENT Sbox quantum circuit.