Unconditional vs. Conditional Security

The cryptographic constructions (also referred to later on as cryptographic schemes) are built to stand against adversaries that mount intentional attacks (see Crypt(?)). 

In general, we aim for powerful adversaries: a cryptographic construction that stands against one adversary also stands against weaker adversaries (i.e., adversaries with less capabilities). So, the stronger the adversary is, the better (i.e., more secure) the scheme is.

The most powerful adversary we can think of is unbounded in the sense that he/she can use infinite resources (e.g., unlimited computational power and time). A cryptographic construction that fully stands against an unbounded adversary is called unconditionally secure or information-theoretically secure.

Examples of information-theoretically secure schemes include One Time Pad (OTP) [1] and Shamir's secret sharing scheme [2].

Information-theoretical security is a strong concept that sometimes (in fact, most of the time!) can be neglected in practice. It admits relaxations, such as:

statistical security - maintains the adversarial capabilities unbounded but allows a tiny success probability in breaking the scheme; computational security - bounds the adversary (i.e., the adversary is limited in computational power and time) and allows a negligible probability of success in breaking the scheme.   Statistical security introduces one single relaxation to information-theoretical security: the adversary's probability of success in breaking the scheme changes from zero (no chances at all!) to a tiny value. More precisely, the adversary has a slightly higher probability of breaking the cryptographic scheme a-posteriori than a-priory. To give an example: if an encryption scheme is information-theoretically secure, then the adversary can find the plaintext before (a-priory) or after (a-posteriori) knowing the corresponding ciphertext with exactly the same probability; this means that the ciphertext leaks no information about the plaintext (Note: the length of the plaintext is ignored); if an encryption scheme is statistically secure, then the adversary has a slightly increased probability of finding the plaintext after knowing the corresponding ciphertext (a-posteriori) than before (a-priory); this means that the ciphertext leaks some information about the plaintext.

The adversary's probability of success in breaking the scheme is a function of a statistical security parameter. The probability of breaking the scheme decreases when the security parameter increases, so one has to increase the security parameter to obtain better security. As a tradeoff, a large security parameter usually means more computations, which slows down the process. So, the security parameter gives flexibility by setting the security level and the tradeoff between security and efficiency. The idea behind the security parameter is the same as in computational security, which I will explain next.   

Most of the time, besides accepting a tiny success probability of breaking the scheme, it suffices to consider adversaries with bounded computational power that cannot succeed their attacks in a limited time. This is computational security. Think, for example, of an encryption scheme that only a network of the world-best supercomputers can break in, let's say, 2000 years; such a scheme generally suffices personal or enterprise use for providing data confidentiality.

Computational security is, of course, weaker than information-theoretical security because it introduces two relaxations. However, reasoning about security in terms of efficient adversaries and negligible probability of breaking has its own advantages. In fact, computational cryptography is what most of the standards in place today are designed to aim for.

Information-theoretic security stands against brute force; in particular, an unbounded adversary will eventually try the correct key, but he/she has no way of checking if the key is or is not correct. In fact, the only way to break information-theoretic security (in theory, as its implementation is prone to vulnerabilities) is to find the cryptographic key by some "non-cryptanalytical" means (e.g., steel the key, corrupt the communicating parties). Computational security assumes adversaries with lower capabilities than the ones considered in information-theoretic security; hence, it is weaker (i.e., computational security provides less security). However, information-theoretically secure systems are usually (not always!) poor in practice, while computational cryptography is efficient and thus suitable for real-life usage. For example, this is the case of encryption, for which information-theoretical security requires keys (as least) as long as the plaintext, a constraint that makes it most of the time useless.

As previously explained, computational security bounds the adversary in computational power and time. In addition, the adversary is probabilistic: he/she can toss a coin (e.g., randomly choose between 2 choices with equal probability).

The probabilistic aspect gives the adversary the possibility to break a construction by chance, e.g., in general by guessing the cryptographic key, or, for encryption, by guessing the plaintext; however, the adversary is only allowed to win (i.e., break the scheme) with a probability so small that is negligible. Both the time to succeed the attack and the winning probability are functions of a computational security parameter (here denoted by n). You can think of this security parameter as the length of the cryptographic key: the longer the key, the better the security. The security parameter is handy in practice: to maintain the desired level of security in time by keeping up with the advanced in computation (e.g., according to the Moore's law [3]) or to use different levels of security for different applications. For example, at the moment, one can think about using AES-256 for protecting personal data and AES-512 for protecting sensitive enterprise or medical data; 256 and 512 denote the length of the cryptographic key, and the cryptographic key itself can be thought of as the security parameter. This is the asymptotic approach.

There is also a concrete approach to arguing about security in real life. Sometimes, to simplify, the time to succeed the attack and/or the winning probability are constants, e.g., dependent on the best available computational power at the given moment. Such a simplification - if considered independent from the asymptotic approach and not as an instantiation of the security parameter at a given time - lacks the feature of tuning the security level and the tradeoff with efficiency at need.

An algorithm polynomial in time is an algorithm whose size grows polynomial in the size of the input [4]. In cryptography, it is generally required that the attacks are polynomial in time. The adversaries that win with attacks that run in polynomial time are considered to be efficient. Inefficient adversaries are usually ignored because they (potentially) break a scheme too late (e.g., after the data becomes unclassified, the password is changed, the system is replaced). An adversary that is bounded to run in polynomial time and can toss a coin is called Probabilistic Polynomial in Time (PPT), and it is the most encountered type of adversary in cryptology today.

Note that not only the adversary is polynomial, but the cryptographical construction also runs in polynomial time (e.g., the encryption and decryption algorithms run in polynomial time). Running in polynomial time allows tuning the security parameter n: even if the value of n increases, the scheme remains efficient and hence, feasible in practice (an exponential encryption or decryption algorithm would require too much time for large values of n).

Again, same as for semantic security, the adversary has a tiny probability to succeed in breaking the scheme. So small that is negligible in the security parameter n (w.r.t. a PPT adversary): there exists a threshold n_d such that for all values equal or larger than this threshold n_d, the function is upper bounded by the inverse of a fixed polynomial. Think of the function as the success probability of the adversary at a single run of his/her attack. The adversary is PPT so he/she can repeat his/her attack for a polynomial number of times (not more!). Then, the overall probability of success will never reach 1 (i.e., the adversary will never break the scheme with a probability of 100%). In fact, the probability will remain low. Examples of non-negligible functions are the constants (e.g., 1/2) or the inverse of the polynomials (e.g., 1/n^100). Although a winning probability of 1/n^100 might seem low, the adversary should repeat his/her attack n^100 times to win, which he/she can do because n^100 is polynomial. When thinking of negligible functions we normally have in mind the inverse of an exponential (e.g., 1/2^n) or a polynomial over an exponential (e.g., p(n)/2^n) (Note: the usage of 2 here - 2^n and not 3^n, 4^n, etc. - comes from the binary representation, with 2^n being the total number of keys on n bits). If an adversary wins at one run with probability 1/2^n, then he/she needs roughly 2^n runs, which he/she cannot do. Repeating the attack for p(n) times only with p(n) polynomial does not help because for large values of n p(n)/2^n remains very low. 

Boneh's course [5] given for Coursera is an exceptional resource for learning cryptology, including notions of security such as the ones explained in this post. A comprehensive book (still a work in progress) is available [6]. You can also read more in Kats and Lindell's book, which I have used for years at my lectures as the course book [7]. Videos to support the material from the book are available here [8] (Note: some of the videos [5,8] are available on YouTube).

[1] Wikipedia. One Time Pad (OTP). Available at: https://en.wikipedia.org/wiki/One-time_pad 

[2] Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612-613.

[3] Britannica. Moore's law. Available at: https://www.britannica.com/technology/Moores-law    

[4] Van Tilborg, H. C., & Jajodia, S. (Eds.). (2014). Encyclopedia of cryptography and security. Springer Science & Business Media. Available at: https://www.researchgate.net/profile/Krzysztof-Kryszczuk/publication/230674947_Springer_Encyclopedia_of_Cryptography_and_Security 

[5] Boneh, D. Cryptography I. Available at: https://www.coursera.org/learn/crypto 

[6] Boneh, D., Shoup, V. A Graduate Course in Applied Cryptography. Available at: https://toc.cryptobook.us/ 

[7] Kats, J., Lindell, Y. Introduction to Modern Cryptography, CRC Press. More info: http://www.cs.umd.edu/~jkatz/imc.html 

[8] Kats, J. Cryptography. Available at: https://www.coursera.org/learn/cryptography