# Quantum Time-Memory-Data Tradeoff Attacks on the SNOW-V Stream Cipher
## 3 TMDTO Attack and Quantum TMDTO Attack  
The problem of, efficiently, inverting a random-looking function \(f\) is a fundamental problem in cryptanalysis, where \(f(x)\) is considered as the cipher-text obtained, by encrypting some fixed plain-text \(p\) under the secret key \(x\). In 1980, [PERSON] [15] proposed the well-known time-memory tradeoff (TMTO) technique, to solve this problem. The complexities of [PERSON]'s TMTO attack can be evaluated by looking at three main parameters, i.e., the online time complexity \(T\), the memory complexity \(M\) and the offline time complexity \(P\). The obtained tradeoff curve is \(TM^{2}=N^{2}\), \(P=N\), where \(N\) is the number of possible internal states. A time-memory-data tradeoff (TMDTO) attack is a generalization of the time-memory tradeoff technique, which aims at obtaining a better tradeoff by increasing the number of required data. Generally, a TMDTO attack has two phases: an offline phase, where the mapping table from different inputs to keystreams is constructed and stored, and an online phase, where the attacker has intercepted some keystreams and searches for them in the table, expecting to get some matches and, further, recover the corresponding input. The complexities of a TMDTO attack can be evaluated by looking at four main parameters, i.e., the online time complexity \(T\), the memory complexity \(M\), the data complexity \(D\) and the offline time complexity \(P\). TMDTO attacks on stream ciphers can be divided into two scenarios, according to the function the attacker tries to invert. In the first scenario, the attacker tries to invert the function mapping of the internal states of a stream cipher to a segment of the keystream output. The most classic attacks in this scenario are Babbage-Golic (BG) [16; 17] and Biryukov-Shamir (BS) [18] tradeoffs, with curves \(TM=N,P=M\) with \(D=T\) and \(TM^{2}D^{2}=N^{2},P=N/D\) with \(1\leq D^{2}\leq T\), respectively. A BS-TMDTO attack is an extension of the original attack by [PERSON], by utilizing multiple data points. In the other scenario, TMDTO attacks can, also, be used to invert the function mapping of the initial inputs (e.g., Key and IV) of a stream cipher to a segment of the keystream output. The most classic attacks in this scenario are Hong-Sarkar (HS-TMDTO) [19] and Dunkelman-Keller (DK-TMDTO) tradeoffs [20], both of which have the same curve as a BS-TMDTO attack with \(N=K\times V\). Here, \(K\) and \(V\) denote the number of possible keys and IVs, respectively.  
In 2015, [PERSON], [PERSON], [PERSON] and [PERSON] [21] first analyzed the time-memory tradeoff attacks in the quantum setting, when \(f\) is a permutation, taking into consideration the power offered by quantum algorithms and, particularly, [PERSON]'s algorithm [22]. The attack was extended to the case of random functions in [23; 24]. At FOCS 2020, it was proven, by [PERSON], [PERSON], [PERSON] and [PERSON] [25], that no quantum algorithms with quantum advice and memory less than \(\sqrt{N}\) are better, compared with a simple application of [PERSON]'s algorithm to this problem. Recently, [PERSON], [PERSON], [PERSON] and [PERSON] [26] proposed the quantum version of time-memory-data tradeoff attacks, and improved [PERSON]'s tradeoff curve to \(T^{\frac{4}{3}}M^{2}=N^{2}\) and the time-memory-data curve to \(T^{\frac{4}{3}}M^{2}D^{2}=N^{2}\), respectively. A typical point on this curve is \(T=M=D=N^{\frac{3}{8}}\).