# How to evaluate the minimum complexity of the key recovery when the success probability p is given？

Since the practical security of a symmetric-key primitive is determined by evaluating its resistance against an almost exhaustive list of known cryptanalytic techniques.

My problem is that could we evaluate the minimum complexity of key recovery of a cipher from an information theory perspective when the success probability $$p$$ is given ?

For example: The best single-key attacks against 7-round AES-128 by impossible differential attack that is : Data complexity is $$2^{104.9}$$, Time complexity is $$2^{110.9}$$ and Memory complexity is $$2^{71.9}$$.

Do these numbers have lower bound? We know the upper bound of Time complexity of key recovery is $$2^{128}$$ and the probability of success is 1, so the lower bound of complexity of key recovery determines the difficulties of recovering Key thus maybe exist.

Also if these lower bounds exist maybe the security of different cipher could be comparable directly. If there is any relevant research available I would greatly appreciate it.

• Are you asking about the least possible time it might take? Well, you could start guessing keys, just happen to guess the correct one at first, and so the minimum time taken would be 1 AES operation. Is that what you're asking? Commented Nov 14, 2023 at 13:58
• You should consider probabilities. If you try one key, you have odds $\frac{1}{2^{128}}$ of finding the correct key, and so on. After testing $2^{127}$ keys you will have $\frac{2^{127}}{2^{128}}=0.5$ odds of having found the correct key Commented Nov 14, 2023 at 14:21
• There is somewhat of a disconnect between the title and the question. The body seems to make it clear that the goal is the complexity of key recovery. Key recovery is not the only way algorithms get broken. Other attacks when possible are usually cheaper. Can you clarify this point? Commented Nov 14, 2023 at 15:24
• And, @MarcIlunga the title is a bit complex as researchers did in AES. They counted the necessary operations on the AES and their idea to conclude that it is faster than brute force. Commented Nov 14, 2023 at 15:41
• what does "minimum complexity of recovering all keys" mean? You need to correct and clarify this question. Use mathematical notation as needed. Commented Nov 14, 2023 at 15:46

Even if we reason asymptotically, we don't have a proof that there exists any encryption algorithm such that the difficulty to find the key (with a fixed non-zero probability) grows exponentially with the bit size of the key. That would require proving the $$P\ne NP$$ conjecture.