# Improved Low-Depth SHA3 Quantum Circuit for Fault-Tolerant Quantum Computers
## 3 SHA3 Quantum Circuit
### Quantum Cost Analysis for SHA3
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & **Function** & **\#1 qClifford** & **\#CNOT** & **\#Toffoli** & **\#T Depth** & **\#Full Depth** \\ \hline \multirow{2}{*}{\(\theta\)} & Our method & 0 & 24,000 & 0 & 0 & 79 \\ \cline{2-7}  & [8] & 0 & 17,600 & 0 & 0 & 275 \\ \hline \multirow{2}{*}{\(\theta^{-1}\)} & Our method & 0 & 0 & 0 & 0 & 0 \\ \cline{2-7}  & [8] & 0 & 1,360,000 & 0 & 0 & 25 \\ \hline \multirow{2}{*}{\(\rho\)} & Our method & & & & & \\ \cline{2-7}  & [8] & & & (Not used) & & \\ \hline \multirow{2}{*}{\(\pi\)} & Our method & & & & & \\ \cline{2-7}  & [8] & & & (Not used) & & \\ \hline \multirow{2}{*}{\(\chi\)} & Our method & 3200 & 640 & 1600 & 23 & 12 \\ \cline{2-7}  & [8] & 0 & 14,400 & (Not shown) & 15 & 55 \\ \hline \multirow{2}{*}{\(\chi^{-1}\)} & Our method & 0 & 0 & 0 & 0 & 0 \\ \cline{2-7}  & [8] & 0 & 18,880 & (Not shown) & 18 & 66 \\ \hline \multirow{2}{*}{\(\iota\)} & Our method & 2 & 0 & 0 & 0 & 1 \\ \cline{2-7}  & [8] & 85 & 0 & 0 & 0 & 24 \\ \hline \multirow{2}{*}{\(\chi\)} & Total & 76,886 & 591,360 & 38,400 & 552 & 2020 \\ \cline{2-7}  & Total [8] & 85 & 33,269,760 & - & 792 & 10,128 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparison of quantum resources for the-state-of-art SHA3 quantum circuit implementation and proposed SHA3 quantum circuit implementation. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & **Cipher** & **\#Toffoli** & **\#CNOT** & **\#X** & **\#Full Depth** \\ \hline \multirow{4}{*}{LEA [32]} & 128/128 & 10,416 & 28,080 & 68 & 26,328 \\  & 128/192 & 15,624 & 39,816 & 100 & 39,452 \\  & 128/256 & 17,856 & 45,504 & 130 & 45,057 \\ \hline HIGHT [32] & 64/128 & 6272 & 20,523 & 4 & 16,447 \\ \hline \multirow{2}{*}{CHAM [32]} & 64/128 & 2400 & 12,285 & 240 & 7807 \\  & 128/128 & 4960 & 26,885 & 240 & 19,880 \\ \cline{1-1}  & 128/256 & 5952 & 32,277 & 304 & 23,856 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Quantum resources required for the Korean block cipher proposed in [32]. Table 9 shows the quantum resources needed for the SHA-256 [8] and SM3 [15] hash functions. The results of comparing our SHA3 quantum circuit with the quantum circuits for other hash functions (LSH-256 [14], SHA-256 [8], and SM3 [15]) were as follows:  
The SHA3 quantum circuit proposed in this paper used more X gates and CNOT gates than the parallel quantum circuit of LSH-256 [14] and had fewer Toffoli gates and a smaller T depth and full depth. Compared to the SHA-256 [8] quantum circuit, our SHA3 quantum circuit used more X gates and CNOT gates but fewer Toffoli gates, and the T depth and full depth were smaller. Compared to the Chinese National Standard hash function SM3 [15], the SHA3 hash function used X gates and CNOT gates more and Toffoli gates less, and the T depth and full depth were smaller. Compared to the LSH, SHA256, and SM3 hash function quantum circuits, the proposed SHA3 required the more X and CNOT gates, but the required number of Toffoli gates, T depth, and full depth were lower. In future quantum computing, it is expected that SHA3 will be the most vulnerable hash function according to its depth. On the other hand, in terms of qubits, it is expected that the time to reach the number of qubits required for SHA3 quantum circuit operation will be the longest. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Cipher** & **\#Toffoli** & **\#CNOT** & **\#X** & **\#Full Depth** \\ \hline \multirow{3}{*}{LEA [33]} & 128/128 & 10,248 & 32,616 & 11,152 & 6505 \\  & 128/192 & 15,372 & 46,620 & 17,004 & 7589 \\  & 128/256 & 17,568 & 53,280 & 19,494 & 8580 \\ \hline \multirow{3}{*}{HIGHT [33]} & 64/128 & 5824 & 22,614 & 4496 & 2479 \\ \hline \multirow{3}{*}{CHAM [33]} & 64/128 & 2320 & 13,200 & 2320 & 2615 \\  & 128/128 & 4880 & 28,760 & 4880 & 5307 \\ \cline{1-1}  & 128/256 & 5856 & 34,944 & 5872 & 6594 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Quantum resources required for the Korean block cipher proposed in [33]. (Results for depth reduction compared to Table 5 through quantum resource trade-off).