I think that there are many interesting answers to your question, but I would like to point out what I personally find the most mesmerizing consequence of quantum theory to cryptography.
One of the most fascinating quantum phenomena that has no classical counterpart is no cloning. This essentially means that if you don't have enough information about some quantum state, then you can't prepare more copies of it.
This could be seen (informally) as a restatement of the uncertainty principle: if you could prepare two perfect copies of a system you know nothing about, then nothing prevents you from measuring each copy in a different basis, thereby obtaining knowledge of two mutually unbiased properties (e.g., if you could perfectly copy an electron, then you could measure its momentum in one copy and its position in the other).
No cloning is usually a huge pain. For example, consider e.g. the Miller-Rabin algorithm for primality testing. This is a randomized algorithm, which means that every time you run it it plays out a little differently. Given a prime number, this algorithm will always tell you that it is a prime. Given a composite number, it will still tell you some of the times that it is prime. However, one can prove that his happens with probability which is less than $1/2$. This implies that if you run the algorithm $n$ times on a composite number the probability that it will tell you that it is prime each and every time is at most $1/2^n$. This process is called amplification, and the underlying assumption is that we can always repeat the algorithm. While trivial classically, this assumption does not generally hold in the quantum realm, as the input state might be measured and thus irreversibly destroyed. It was shown by Marriot and Watrous that BQP algorithms can still be amplified this way, but the way to do so is highly non-trivial.
As you might have expected, now comes the "lemons to lemonade" stage. Because if cloning states is impossible, might we leverage that to our advantage, say, in order to design things that we don't want people to make copies of, such as money?
Amazingly, this idea predates most of quantum computation and information. As early as 1968, Steve Wiesner proposed applying no-cloning to implement money that is physically impossible to forge. More amazingly, his construction is extremely simple and only requires the ability to apply local Hadamard gates (and consequentially, the money is encoded into a completely separable state). Unfortunately, as the story goes, it seems that Wiesner was not able to publish his breakthrough for more than a decade.
The applications of no-cloning has since been extended greatly, and there is ongoing research of very natural further problems such as public quantum money (in Wiesner's scheme, only who created the money can verify it. This merits the question: is it able to make money that anyone can verify but no one could forge) (see also), quantum copy protection, uncloneable encryption, one time signature tokens, etc.. These are all fascinating primitives which are classically impossible, but might be possible using quantum computation (under some mild computational assumptions). The current state of the art is that almost all such constructions either rely on strong (or just irregular) assumptions, or on the existence of some unrealistic oracle. But keep in mind that these questions are relatively new, and the research involving them is very active!