## 2 Related Work
### Evolution of Cryptanalytic Time-Memory Trade-Offs  
The first application for time-memory trade-off to cryptanalysis was introduced by [PERSON] [7]. Prior to performing the attack, the Hellman table must be constructed. For this purpose, \(m\) starting points are chosen independently at random from the set of possible passwords. Each password in the set of starting points is transformed by repeatedly applying a hash function followed by a new type of function called a reduction function, typically denoted as \(R\). The two functions are sequentially applied for \(t\) times to form a chain. The first (starting point) and last (endpoint) elements of the chain form a new entry in the Hellman table, and the table is then sorted on the end points to allow for a fast search using a binary search algorithm. Although [PERSON]'s method allows the quick inversion of hash functions, it still suffers from a few practical limitations. One limitation was noted by [PERSON] and was referenced in the book _Cryptography and Data Security_[27]. [PERSON] observed that the search time is influenced by the number of reads on the hard disk and proposed to reduce the time by forcing the endpoint of a chain to satisfy a specific property such as a point that begins with a fixed number of zeros. In other words, the stopping condition for computing the endpoint of a chain is no longer reaching the desired value of \(t\); instead, it is reaching an endpoint that satisfies a specific property. Such an endpoint is called a distinguished point, which leads to chains of different lengths. This, indeed, allows us to reduce the number of lookups to the hard disk, but at the same time, it introduces additional challenges when dealing with merges in the constructed chains. Those merges are encountered when at some point in at least two chains we come across an identical value. Starting from this value, the chains are identical. This has been a common issue in cryptanalytic time-memory trade-offs since they were first introduced in 1980. Rainbow tables [6] introduced a modified structure for the table construction that uses a different reduction function at every step of the chain generation process. This slight change helps to identify chain merges more easily. With rainbow tables, if a merge is identified in at least two chains, the merge will occur in the same column in both chains. When using rainbow tables for cracking LM Windows hashes, [PERSON] [6] demonstrated that 99.9% of all alphanumeric password hashes (237) could be cracked in just 13.6 s. This high crack rate is due to notable algorithmic weaknesses in LM hashes. In comparison, the approach using distinguished points [27] required 101 s to achieve the same result. Rainbow tables were further improved over the years. In 2008, [PERSON] et al. [28] introduced the concept of checkpoints, which are some positions on the chains where a test is applied. This test is typically a parity check that allows filtering out false alarms without regenerating the chains from scratch. Another improvement is an optimal storage for rainbow tables, which was proposed by [PERSON] et al. [29]. The proposed approach is a new method for storing the endpoints of rainbow tables called compressed delta encoding. This approach aims to significantly reduce the memory required for storing these tables compared to existing methods. A more recent improvement to rainbow tables is the one proposed by [PERSON] et al. [30]. They utilized quantum computing and [PERSON]'s algorithm to improve the efficiency of the rainbow table attacks by developing a quantum rainbow table called QIris. The generation of the quantum rainbow table in QIris involves the classical precomputation of rainbow chains using multiple reduction functions. The final plaintexts of these chains are then processed using a simplified hashing method, and their resulting 16-bit integer representations are organized into buckets based on their value ranges.