Cryptography is the study of how to send messages so that only the intended reader can read them. Usually, that is based on the intended user having a secret key.
One kind of system, called a code, uses code words to stand for other words. For example, a particular general might be referred to as "shark."
Another kind of system, called a cipher, works at a level below that of words, such as individual characters. The romans employed a system, called a Caesar cipher, where each letter is replaced by another.
A code or cipher is founded on the belief that an unintended reader, called an eavesdropper, cannot read encoded or enciphered messages.
For ciphers, we say that the intended reader deciphers a message, while an eavesdropper decrypts a message.
The original message is called the plaintext and the enciphered message is called the ciphertext.
For most of human history, cryptography had no firm foundation. Cryptosystems were chosen based solely on intuition. As a result, encrypted messages were often read by eavesdroppers. Caesar ciphers are so easy to break that newspapers publish short enciphered texts as a puzzle for readers to break.
One lesson taught over and over by history is that you must not base the security of a cipher system on the assumption that an eavesdropper does not know that the message is enciphered, or that he/she does not know the cipher system that was employed. Security come solely from keys.
A firm foundation for cryptography needed to wait for the advent of information theory. The idea is to prove that an eavesdropper who does not possess the key does not have enough information to decrypt messages.
A cipher based on that is called a one-time pad.
Imagine that a message is a sequence of bits, 0's and 1's. A pad is a sequence of bits chosen by a random process that selects each bit independently, with 0 and 1 chosen with equal probabilities of 1/2.
To encipher a message, just take a bitwise exclusive-or of the message with the pad. For example:
| message: | 10011101 |
| pad: | 00101100 |
| enciphered message: | 10110001 |
To decipher the message, a receiver just needs to take its bitwise exclusive-or with the pad. Enciphering and deciphering are the same operation because exclusive-or with a given bit is its own inverse.
But, as the name one-time pad suggests, the pad can only be used to send one message. After that, it should be destroyed.
That requires users to share very long pads if they intend to send much information to one another, making the one-time pad expensive to use.
When messages are sent using a one-time pad, an eavesdropper who does not know the pad can learn nothing except the length of a message.
But if the pad is used twice, the system loses its guarantee of security.
Information theory comes into play in ciphers partly because messages have redundancy, a concept from information theory.
An example of redundancy in English is that the letter q is almost always followed by u. It is redundancy that allows you to reconstuct text where some of the letters have been smudged.
A cipher system removes or hides redundancy.
But we must assume that the original message has enough redundancy that an eavesdropper who correctly guesses the key knows that the key is correct. An incorrect key would, presumably, lead to a result that is nonsense.
The one-time pad is based on an eavesdropper not having enough information to decrypt an enciphered message.
But there is another way to make a cipher system secure: ensure that an eavesdropper does not have enough time to decrypt a message. That is, make decryption a problem that is expensive to solve.
That allows you to publish information about how to encipher a message, since security is based on difficulty of decryption, not on keeping the cipher secret. A system like this is called a public-key cipher.
There still needs to be a key for deciphering messages, and it needs to be kept secret. That means there are two keys, one to encipher (public) and one to decipher (private).
Early work on public-key cryptography attempted to choose a cipher so that the decryption problem was NP-complete. But that did not work out, as we see now.
Let's look at the Decryption Problem: given ciphertext C, compute the corresponding plaintext P.
There is a decision problem that has the same difficulty as decryption, which we call the Bit Decryption Problem (BDP).
Input. Ciphertext C and nonnegative integer n.
Question. Is the n-th bit of the plaintext P corresponding to C a 1?
It is easy to do a polynomial-time Turing reduction from the Decryption Problem to BDP, and also from the BDP to the Decryption Problem.
BDP must be in NP. The evidence is the deciphering key. Using that key, the algorithm deciphers C, yielding plaintext P.
Then it checks that the key worked, either by using redundancy or by encoding P and testing whether the result is C. Finally, it looks at the n-th bit of P.
Now let's look at the complement of the BDP:
Input. Ciphertext C and nonnegative integer n.
Question. Is the n-th bit of the plaintext P corresponding to C not a 1?
But that question is equivalent to asking whether the n-th bit of P is a 0, and that is effectively the same problem as BDP. So the complement of the BDP is in NP. That is, BDP is in NP ∩ CoNP.
The upshot is that a public-key cipher system must be based on a problem that is in (NP ∩ CoNP) − P.
If NP ≠ CoNP then no NP-complete problem can be in NP ∩ CoNP. Public-key ciphers must be based on something weaker than an NP-complete problem.
The problem of finding the prime factors of an integer (converted to a decision problem) is in NP ∩ CoNP, and is conjectured not to be in P, so it is a good candidate.