# Quantum Time-Memory-Data Tradeoff Attacks on the SNOW-V Stream Cipher
## 5 Quantum TMDTO Attacks on SNOW-V  
[PERSON]'s algorithm is a quantum computing algorithm invented to search from an unstructured database, which can be mathematically modeled as follows.  
**Problem 1** ([31]).: _Let \(f:\left\{0,1\right\}^{n}\to 0,1\) be a binary function on the set of \(n\)-bit strings. The problem is to find an element \(x\in\left\{0,1\right\}^{n}\), such that \(f(x)=1\)._  
Let \(f\) be a quantum circuit or a quantum oracle with the promise \(|f^{-1}(1)|=1\); [PERSON]'s algorithm can solve this problem above with \(O(2^{\frac{n}{2}})\) evaluations of \(f\). Comparing to \(O(2^{n})\), which is the best asymptotical complexity that a classical search algorithm could achieve for an unstructured database, [PERSON]'s algorithm obtains a quadratic speedup and is significantly better. Thus, it is widely recognized that doubling the key size of the symmetric ciphers will be enough to maintain the same security level against quantum adversaries.  
In [25], [PERSON] et al. proved that even with quantum advice, \(TM+T^{2}=N\) is required for an algorithm to invert random functions. In [26], [PERSON], [PERSON], [PERSON] and [PERSON] improved the [PERSON]'s tradeoff curve to \(T^{\frac{4}{3}}M^{2}=N^{2}\) and generalized the time-memory-data tradeoff curve to \(T^{\frac{4}{3}}M^{2}D^{2}=N^{2}\), respectively. The quantum TMDTO attack has a circuit size of about \(O(f)\) qubits. A typical point on this curve is \(T=M=D=N^{\frac{8}{8}}\). As we know, the tradeoff curve for a DK-TMDTO attack is the same as a BS-TMDTO attack with \(N=K\times V\) and \(1\leq D\leq V\). Here, denote \(K\) and \(V\) as the numbers of possible keys and IVs, respectively. Now, we combine a quantum time-memory-data tradeoff attack with a DK-TMDTO attack, to analyze the stream cipher SNOW-V.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Sampling Resistance** & **Integer Parameter** & \(T\) & \(M\) & \(D(d,d^{\prime})\) & \(P\) \\ \hline \(R=2^{-128}\) & \(r=1\) & \(2^{384}\) & \(2^{384}\) & \(2^{384}(2^{192},2^{192})\) & \(2^{384}\) \\ \hline \(R=2^{-256}\) & \(r=1\) & \(2^{320}\) & \(2^{320}\) & \(2^{576}(2^{288},2^{288})\) & \(2^{320}\) \\ \hline \(R=2^{-384}\) & \(r=1\) & \(2^{256}\) & \(2^{256}\) & \(2^{640}(2^{320},2^{320})\) & \(2^{256}\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: BG-TMDTO attacks on SNOW-V with BSW sampling.  
As for the stream cipher SNOW-V, we have \(N=K\times V=2^{256}\times 2^{128}=2^{384}\). That is, we obtain a tradeoff curve for SNOW-V, as \(T^{\frac{4}{3}}M^{2}D^{2}=2^{768}\) and \(1\leq D\leq 2^{128}\). It is easy to see that a typical point on this curve is \(T=M=D=2^{144}\). However, it does not satisfy the restriction \(1\leq D\leq 2^{128}\). Table 3 lists the complexities of quantum time-memory-data tradeoff attacks on SNOW-V. The results show that in the quantum setting, a TMDTO attack needs memory space of at least \(O(2^{170,67})\), in order to offer an attack on SNOW-V that is faster than [PERSON]'s algorithm. In other words, a quantum TMDTO attack on SNOW-V offers, strictly, better online time complexity than [PERSON]'s algorithm for any \(M>2^{170,67}\).