Achieving higher success probability in time-memory trade-off cryptanalysis without increasing memory size
The time-memory trade-off cryptanalysis for block ciphers with a search space of size 2(N) (N: key length) cannot achieve a success probability exceeding 63%. This is caused by some unavoidable overlapping of keys in the space. For elevating the success probability of finding the correct key, a larger search space is necessary. That is, the increase of time complexity for precomputation would be inevitable. This paper theoretically shows, however, no further price is required for the size of look-up tables for the number of encryptions for searching for the key that matches the given ciphertext - plaintext pairs. This theory is confirmed by some empilical results.
success probability time-memory trade-off time complexity space complexity