# What needs to be proved for a cryptosystem to be secure?

For example showing that it is easy to produce ciphertext from plaintext but is difficult/impossible to get plain text from ciphertext.

I am asking in general but am more interested in asymmetric crypto.

Would these things be different from what I need to prove to show it is a good digital signature?

• – fkraiem Jul 17 '15 at 5:58

Not every cryptosystem is provably secure, in fact most aren't. Even among those that are the security is only proved under a limiting set of assumptions, not in a completely general sense.

Of those that are provably secure, what's needed is a formal goal, and a proof that the system accomplishes the goal with zero or more formally stated assumptions.

For example, IND-CCA (indistinguishability under chosen ciphertext attack) and IND-CPA (indistinguishability under chosen plaintext attack) are goals with different assumptions about the capability of the attacker. Not every cryptosystem will satisfy either or both or needs to do so. Many will satisfy neither and still be secure. Others will satisfy both but be insecure due to other factors, such as implementation bugs or the application of rubber hose cryptanalysis. See the link in fmraiem's coment for more (Easy explanation of "IND-" security notions?).

As an example from public-key cryptography the Diffie-Hellman key exchange system can be proven to depend upon the security of the Computational Diffie-Hellman Problem (CDHP). If the CDHP is hard, Diffie-Hellman key exchange is secure (under the assumptions of Diffie-Hellman, eg that man-in-the-middle attacks are impossible). If the CDHP is easy, then Diffie-Hellman key exchange is insecure even if the assumptions hold. CDHP is thought to be hard, but this has not been proven. Diffie-Hellman key exchange in practice includes other aspects to ensure that its assumptions can hold, such as using certificates to authenticate the parties and avoid man-in-the-middle attacks.

• One can build a key exchange system that "can be proven to depend upon the security of the Computational Diffie-Hellman Problem (CDHP)" (via Theorem 6), but as far as I'm aware, the security of Diffie-Hellman itself as a key exchange system against passive adversaries is not known to follow from the hardness of the CDHP. $\;$ – user991 Jul 17 '15 at 8:13

It always depends on what you mean by secure, but note that, as SAI Peregrinus said in the other answer, not every cryptosystem is provably secure.

For example showing that it is easy to produce ciphertext from plaintext but is difficult/impossible to get plain text from ciphertext.

The property you describe here is called one-wayness (OW), and it is expected that any encryption scheme fulfills this property; otherwise, it is a rather crappy scheme, isn't it?

However, it is just a very minimal requirement for an encryption scheme, and it is often considered not enough. There is a stronger security goal called indistinguishability (IND), which dictates that the encryption scheme should not permit an adversary to distinguish which message (from two possible options, $m_0$ and $m_1$) is encrypted by a given ciphertext.

In a real setting, this basically means that even if the adversary cannot extract the original message from the ciphertext, if he suspects that the ciphertext is the encryption of two possible messages, he should not be able to guess correctly which one it is.

Of course, these are security notions from the provable security field. As SAI Peregrinus mentioned, there are many other aspects that can be exploited, such as side-channel attacks, implementation bugs, etc.

Would these things be different from what I need to prove to show it is a good digital signature?

Yes, because the security objectives are different. With digital signatures you are not trying to achieve confidentiality, as in an encryption scheme, but authentication and integrity. Basically, what you want with a digital signature is that the adversary cannot forge signatures, which is called unforgeability.