Provable security

Provable security is a concept in modern cryptology. In the history of cryptography, there are many examples of systems that have been held by their inventors for sure, but could still be broken. It is therefore desirable to satisfy itself by a proof in a formal way from the security of a system. These must be formalized both the cryptographic system and the achievable security.

Perfect security

Claude Shannon defined in 1949 perfectly secure encryption method and showed the conditions under which they exist. A perfectly secure encryption method is characterized in that a generated key with him text allows no inference on the corresponding plaintext. In such a method is proven mathematically, that an attacker knows the key text, apart from the length of the plaintext can not gain further information about this. He can not decrypt or even break the entire process the ciphertext so. Shannon proved that the one-time pad is perfectly secure.

Asymptotic safety

An information-theoretic proof guarantees security against an attacker that are not limited in their processing power. Such an attacker could, however, simply try all possible keys in a method such as AES. With real existing computers but that would take too long. To make the concept of security, realistic, therefore the attacker is limited in processing power, depending on the key length used (or a security parameter). Then it is shown that the system is safe against such invaders. Therefore shown only that the effort for an attacker grows much faster than the cost of the user. By properly selecting the key length attacks can be virtually eliminated. However, the key length must be adapted to the available computing power, which is one of the reasons that the key length formerly used for RSA of 768 bits is now considered unsafe. Because only the asymptotic behavior is investigated, ie, the security also asymptotically or computationally.

The security of the system can not be proved without further assumptions for most cryptographic methods. One of the earliest assumptions used is that the factoring problem is hard. The security proof is then a reduction between the breaking of the system and solving the problem. For example, it can be proved that any attacker who can calculate from the public key of the RSA cryptosystem, the secret, solve the factoring problem can (more precisely, can be constructed from a successful attacker an efficient solver ). However, since there can not be such a solver according to assumption that there can be no successful attacker. Security no longer means here so that it is completely impossible for the attacker to break the system, but that this is virtually impossible. In other words, its success probability is negligibly small.

Concrete safety

In asymptotic security proof is only shown that a system is safe from a certain value of the security parameter ( key length ). If you want to instantiate such a system, but a concrete parameters must be chosen. For this, the evidence must be performed more accurately and a tight upper bound are given for the success probability of the attacker as a function of the used resources (running time, number of oracle queries ). Can such a function be specified, one speaks of concrete security.

Example

The ElGamal encryption scheme is IND - CPA secure assuming that the decisional Diffie -Hellman problem is difficult. The proof consists of a reduction in the from each successful attacker against the security of the system solver is designed for the DDH problem. Because DDH was assumed to be hard, making it clear that such an attacker can not exist.

Given an attacker A, none of which is known, except that he wins the IND - CPA experiment against ElGamal. So when he receives a public key, it outputs two messages. If you give him then encrypt one of the two under the public key, he can say with probability which message was encrypted.

For this attacker A can now be constructed as follows a solver S for DDH. This includes a description of a group of producers and a triple as input. S now simulates the key generation and are a public key to A. The corresponding secret key S does not know, but that may not know A. A gives after some time of two messages. S must now simulate the encryption. He chooses a random bit and sets the cipher to. The attacker A then responds a bit. Is now, so the cipher is indistinguishable from a normal generated. Is a random group element, so the attacker can only guess and wins with probability 1/2. The strategy of S is therefore as follows: Was A successful and returns the correct bit, S suspected that. If A is false, S suspected that a random element was. The success probability of S is then.

Discussion

The paradox of provable security is that a proven to be safe system is not necessarily really sure. The reason is that several assumptions and formalizations are needed for a proof. The system, the attacker and the security objective must be described formally ( such as IND - CPA security for encryption ) and the proof is only a reduction of a problem whose gravity was adopted. An attacker who is stronger than assumed in the proof, the system can break so perhaps. So it may happen that the safety objective was not formulated sufficiently, so the attacker would be sufficient a lesser success. If the security target, for example, " No attacker is from a ciphertext can derive the plaintext ," the evidence does not state an attacker who wants to learn only the first three letters of the plaintext. Another problem is that the real cryptosystem not exactly formal maps, mistakes were made because either in the implementation of formal and in formalizing an already existing system. A more likely way to break the system does, is to solve the mathematical problem, which is the underlying security. Finally can just use the evidence be wrong. Despite these numerous problems security proofs are a valuable tool in modern cryptology.