I have so far seen the proof by reduction technique to prove the security guarantee of cryptosystem where we consider breaking the cryptosystem as hard as solving a difficult mathematical problem. What are the other proof techniques used to prove the security of the Cryptosystem? It would be beneficial if the technique is briefly stated.


1 Answer 1


The question mentions proof by reduction to a difficult mathematical problem (e.g. Computational Diffie–Hellman). That's not the only common use of proof by reduction to prove the security of a cryptosystem: instead of hardness of a math problem, we often assume existence of a cryptographic building block with some assumed cryptographic property, like a block cipher computationally undistinguishable from a random permutation when the key is random, or a hash assumed to be accessible to adversaries only as a random oracle.

For some systems we have direct proof of perfect security by an information-theoretic argument, e.g. establishing that no information about plaintext can be gained from ciphertext in the One Time Pad. Problem is, the systems which security is provable by that line of proof all need a secret key as large as the whole plaintext ever transmitted (demonstrably if plaintext is assumed random), and thus are impractical. In particular, none can be a secure cipher, by the mathematical definition of that. So for proof of practical cryptosystems, the information-theoretic line of argument must be used in combination with proof by reduction and assuming something.

I know no other mathematical security proof method for cryptosystems. I know no practical cryptosystem with a full mathematical proof of security. And even if we cut corners on practicality, existence of a secure cipher would imply P≠NP, and we are not there.

However we also have arguments of security. We can design a cryptosystem or building block (such as a block cipher or hash) with parameters (in particular, number of rounds and width of variables), examine how difficulty of breaking it by known cryptanalytic methods become harder when these parameters grow, and convince ourselves that this trend will go on (this is the hardest and most uncertain); then conclude that with certain large-enough parameters we are safe from these known attacks.

With the rare exception of the One Time Pad, perhaps coupled with Quantum Key Distribution, all deployed cryptographic systems that it's reasonable to trust use this later line of argumentation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.