# SPEEDY Quantum Circuit for Grover's Algorithm
## 4 Evaluation
### Security Strength Analysis for SPEEDY  
The post-quantum security strength for SPEEDY is evaluated based on the security strength category presented by NIST [3]. We calculate the cost with the same calculation as [PERSON] et al. [4]. That is, the cost is calculated to (total gate \(\times\) total depth). In NIST, the cost of AES-128, 196, and 256, which are security strength standards, was estimated as AES-128:2170, AES-196:2233, AES-256:2298. The following are security strength categories presented by NIST based on AES-128, 196, 256: \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Cipher**} & \multirow{2}{*}{\(r\)} & \multirow{2}{*}{**Qubits**} & \multicolumn{6}{c}{**Gates**} & \multirow{2}{*}{**Depth**} \\ \cline{3-3} \cline{5-10}  & & & CCCCCX & & & & & & \\ \hline \multirow{5}{*}{SPEEDY-\(r\)-192} & 6 & 3648 & 1536 & 3072 & 9216 & 8832 & 11,520 & 855 & 859 \\ \cline{2-10}  & 7 & 4224 & 1792 & 3584 & 10,752 & 10,304 & 13,632 & 1018 & 1002 \\ \cline{2-10}  & 14 & 8256 & 3584 & 7168 & 21,504 & 20,608 & 28,416 & 2118 & 2011 \\ \cline{2-10}  & 28 & 16,320 & 7168 & 14,336 & 43,008 & 41,216 & 57,984 & 4346 & 4029 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Quantum resources for SPEEDY. * Level 1: Block ciphers using a 128-bit key (e.g., AES 128) require computational resources that are greater than or comparable to those required for key search. * Level 3: Block ciphers using a 192-bit key (e.g., AES 192) require computational resources that are greater than or comparable to those required for key search. * Level 5: Block ciphers using a 256-bit key (e.g., AES 256) require computational resources that are greater than or comparable to those required for key search. [PERSON]'s algorithm can reduce the computational complexity from \(O(N)\) to \(O(\sqrt{N})\) for symmetric key cryptography with an \(n\)-bit key (i.e., \(N=2^{n}\)). This search algorithm increases the probability of finding the right key by repeating oracle and diffusion, and the quantum circuit is used in the oracle operation for encryption and decryption. Since the quantum circuit is a reversible circuit, decryption can be performed by reverse operation (i.e., encryption resource = decryption resource). Therefore, the total quantum resource used in the [PERSON]'s algorithm is calculated as \(\lceil\)key size/block size\(\rceil\times(Encryption+Decryption)\times\) number of iterations (i.e., \(R\times 2\times\) Table 1\(\times\lfloor\frac{\pi}{4}2^{\frac{n}{2}}\rfloor\)). The [PERSON]'s algorithm resource for SPEEDY is shown in Table 2. We compute the [PERSON]'s key search cost by decomposing the non-\(Clifford\) gate into the \(T+Clifford\) gate from the estimated resource. Since the X gate and CNOT gate are the \(Clifford\) gates, only the Toffoli gate and multi-controlled X gate are decomposed into \(T+Clifford\) gates. One Toffoli gate is decomposed into \(7\)\(T\) gates and \(8\)\(Clifford\) gates, and multi-controlled \(X\) gates are decomposed into \((32\times C-84)\)\(T\) gates (C: number of control qubits). In a classic computer, SPEEDY-\(r\)-192 provides 128-bit security when \(r=6\) and 192-bit security when \(r=7\). However, both SPEEDY-6-192 and SPEEDY-7-192 provided 128-bit security in a quantum computer. In response, we performed encryption with more rounds \(r\) to check the strength of security in quantum computers. However, even if the number of rounds of \(r\) was increased as in Table 2, security was maintained at level 1. Contrary to expectations, increasing the number of rounds did not provide higher security. In other words, it can be confirmed that it is difficult to increase the security strength in quantum computers by increasing the number of rounds of encryption. It is also very inefficient because the number of rounds \(r\) must increase exponentially to enhance security in quantum computers. Simply put, the classic method of increasing security by increasing the number of rounds does not apply to quantum computers.