Computational security – Encryption and Decryption

4.4 Computational security

Compared to information-theoretical security, the concept of computational security is weaker in the sense that such cryptographic schemes can, in principle, be broken if Eve has enough time and sufficient computational resources.

However, the amount of computations needed to break a computationally secure scheme is so large that a break is absolutely infeasible in practice. As an example, if a scheme cannot be broken with a probability higher than 10−40 in 300 years using the fastest supercomputer available today (or in the near future), then that cryptographic scheme is sufficiently secure for all practical purposes.

On the positive side, computational security bypasses the limitations of perfect secrecy. As discussed in [97], perfect information-theoretical security suffers from the required key length: the secret key that Alice and Bob need to exchange before they can start communicating securely must have the same length as the overall length of all messages that will be ever encrypted with that key. Computational security overcomes this problem by weakening the notion of perfect secrecy in the following two aspects:

• We guarantee security only against attacks that Eve can execute in a practically relevant or feasible amount of time. In the context of cryptography, such (attack) algorithms are also called efficient and we will see shortly what that specifically means.
• Eve might succeed with some very small probability. In computationally secure encryption schemes, the ciphertext does carry a tiny bit of information about the plaintext so that, unlike with perfect secrecy, the probability of Eve succeeding is a bit higher than her guessing probability. However, this probability is still so tiny that Alice and Bob need not be concerned about it in practice.

We’ll now analyze the situation that arises if Eve uses randomized algorithms to attack Alice and Bob. These algorithms are not always faster than their deterministic counterparts, but there is a certain probability that they are. This can improve Eve’s overall success probability, so Alice and Bob should be aware of these algorithms.