How Not to Learn Cryptography

People often ask me how to get started in cryptography. What's interesting is that most of the time they also want to know how I personally got started. This is interesting to me because it suggests that people are looking for more than a list of books or papers to read or set of exercises to solve; they're really looking for a broader strategy on how to learn the subject. In this post I'll discuss some possible strategies.

First, let me stress that I am only considering strategies for learning crypto design and theory. Also, what I have in mind when I say "learning crypto" is not getting to the point of understanding an average paper, but getting to the point of generating such papers yourself (or at least the ideas in them). If your end goal is crypto engineering then the strategies may or may not be helpful---I'm not an expert so I can't really say either way ( though I'd like to think that improving your understanding of how primitives and protocols are designed can be helpful).

I should say from the outset that the way I personally got started in cryptography is probably one of the worst possible ways to do it. It was highly inefficient and had a very low probability of success. This was mainly because I didn't have the proper background when I started and I didn't have the right resources at my disposal. These two things are very important and one of two things is likely to happen if you don't have them: (1) it will take you so long that you'll get fed up and give up; or (2) you'll become a crank (and believe me, there are a ton of cranks out there selling crypto products).

When devising and implementing your strategy, you should keep these outcomes in mind because it will be very important to avoid them at all costs.

How to Do It

The best strategy for learning crypto design and theory is to get a Ph.D. at a University with a cryptography group. Getting a Ph.D. in some random field like mechanical engineering or biology does not count! If you are interested in symmetric cryptography (i.e., block cipher and hash function design and cryptanalysis), then a good place to start are European Universities since a large fraction of the experts are there. If you're interested in crypto theory then the US or Israel. Of course there are strong groups in each area everywhere.

If you have found a University and are trying to evaluate the group is, then a very rough sanity check is to look at their publication record. If this is a theory group then you should be looking for CRYPTO, Eurocrypt, Asiacrypt, TCC, FOCS, STOC publications. If this is a more applied group, then you should be looking for publications at CCS, CHES, IEEE Security and Privacy (also known as Oakland) and Usenix Security. CRYPTO, Eurocrypt and Asiacrypt are not particularly good indicators of quality for applied crypto. If this is a symmetric crypto and cryptanalysis group then you should look for papers at Fast Software Encryption (FSE) and Selected Areas in Cryptography (SAC). Similarly to applied crypto, CRYPTO, Eurocrypt and Asiacrypt are not necessarily good indicators of quality in this area.

But you shouldn't get too caught up in this, however. The publication system in cryptography is screwed up so you shouldn't necessarily dismiss group $A$ because it has less STOC papers than group $B$; or less CCS papers than group $C$. This is just a very coarse metric that---absent of any other signals---can be used to distinguish between very good groups and very bad ones. Another good thing to check is where the students that graduate from that group end up. Do they end up with jobs that you would like?

So why is getting a Ph.D. from a good group the best strategy? Simply because it is the most efficient way to learn the material. The background needed for crypto is not part of a traditional education, neither in math nor in computer science, so it's unlikely that you'll have learned what you need in undergrad. So you have two choices: (1) learn it on you own; or (2) learn it in graduate school.

In grad school you will have a set of classes carefully chosen and prepared for you. You'll have an advisor that will guide you through the process, telling you what you need to learn, what you don't need to learn, what your weaknesses are, what you need to improve, what problems to work on and the best strategies to solve those problems. You'll also have fellow students that will help and motivate you throughout.

Note that for most Ph.D. programs in computer science you don't have to pay anything. Your tuition is taken care of by the department or by your advisor's grants. In addition, you receive a stipend which takes care of housing, food etc. So if you're in a position to devote $5$ years of your life to learning cryptography, then I think grad school in a crypto group is by far the best strategy.

How Not to Do It

So you can't go to grad school or you can but somewhere without a crypto group and you still really want to learn crypto design and theory. Here is one possible strategy---the one I used.

I'll assume you have a standard systems-focused computer science undergrad degree. In my case, for example, I had a strong systems background in undergrad (e.g., compilers, OS, networking, architecture) and a very weak theory background (just calculus, intro to algorithms and a linear algebra class so bad no one ever attended). To be brutally honest, this kind of background is useless for cryptography and if this is the point at which you're at then you have to understand that you'll be starting from scratch.

There are three things you should be shooting for: (1) developing mathematical maturity; $(2)$ learning how to debug; (3) acquiring the basics.

By mathematical maturity, I mean the ability to understand and use basic mathematical language, notation and concepts. It's basically having the right context in place for doing math. Knowing how to parse mathematical statements and proofs and generally-speaking, knowing how to read between the lines and how to fill in the missing pieces.

By debugging, what I mean is that you have to get to a point where you can reliably tell whether you have fully understood some idea or not. When you are starting out and working alone, this is extremely difficult especially for an area like cryptography which can be so subtle. If you don't acquire this skill, however, you will end up a crank: that is, someone that has read a lot, understood very little, and is completely unaware of how confused and wrong they are. Many people who are self-taught end up like this so you have to be careful.

The problem with most of the advice given for learning a hard subject is that they focus on the third stage; typically by pointing to papers or books. But papers and books are useless if you don't have the first two skills.

Acquiring Mathematical Maturity

Of course, the easiest way to acquire mathematical maturity is to get an undergraduate education in math.

Maturity is probably the skill that takes the longest to acquire. Math and theoretical areas of computer science are expressed through definitions, theorems and proofs. A definition is a precise description of some object or process. A theorem is a precise statement concerning some object or process and a proof is an argument as to why the statement is true. You should be comfortable with this paradigm because everything you will see further down the line will be expressed this way. But understanding this paradigm means you'll have to be comfortable with basic notions like quantifiers (i.e., existential and universal), basic proof structures (e.g., direct and by contradiction), basic logic, elementary probability, etc.

By comfortable, I don't mean a casual, superficial understanding of these things. What I mean is you should be able to properly formulate definitions, theorem statements and proofs yourself and be able understand why some formulations are better than others.

You shouldn't think of mathematical formalisms as pedantic, boring and academic. Yes, in some cases they can be overkill because you may have a good intuitive understanding of an idea, but there will be times where your intuition fails and that's when having a good grasp of the formal approach will help you. Cryptography, in particular, is very unintuitive so formalism is even more important---especially when you are starting out.

Most books on cryptography will not help you acquire mathematical maturity because it is assumed that the reader has it. If you are coming from a purely systems background though, you may not have had the opportunity to develop it (as was my case, for example). And reading math books is usually even worse since mathematicians learn this stuff very early on.

So what can you do? The approach I took was to just read everything I could find in math, theoretical computer science and cryptography. Once in a while, I would get lucky and find a paper with a decent explanation of some basic concept (e.g., some basic probability argument or a slightly more detailed proof structure) but most of the time I had to reconstruct the missing the pieces and context on my own.

Obviously, this is easy to do when you have the basics but it is incredibly difficult and frustrating when you don't. As you can imagine it took forever to fill in the gaps in my knowledge. Therefore, the ideal approach would be to find a book or lecture notes that focus on this stuff. And---luckily for you---Timothy Gowers has written an excellent series of blog posts on these very things so you should read them:

1. Basic Logic
   1. And & Or
   2. Not
   3. Implies
   4. Quantifiers
   5. Negation
   6. Converse and contrapositive
   7. Handling variables
   8. Summary
2. Functions
   1. Injections, surjections, etc.
   2. Co-domains, ranges, images
3. Permutations
4. Definitions
   1. Definitions
   2. Alternative definitions
5. Equivalence relations

Debugging

Being able to detect whether you've made a mistake is an important and difficult skill to acquire in any subject. This is exacerbated in security and cryptography since we cannot ascertain the security of something experimentally. Luckily, in crypto we do have a methodology for debugging: namely, provable security . The provable security paradigm (or more appropriately, the reductionist paradigm) consists of the following steps. One first formulates a security definition that captures the security properties/guarantees that are expected from the system. Then, one describes a cryptographic scheme/protocol for the problem at hand. Finally, one proves that the scheme/protocol satisfies the security definition (usually, under some assumption).

The provable security paradigm originated in the 80s' and has been used ever since in the cryptography community to analyze the security of many primitives. There are many benefits to this paradigm but one of the main ones is that it is a great debugging tool. When trying to prove the security of your primitive, you will sometimes find that the proof will not go through for some reason and, more often than not, it is because of a subtle weakness in your protocol that you did not pick up when first designing it.

I want to stress that the provable security paradigm is not foolproof and that it has its limits. For example, there are entire areas of cryptography like block cipher and hash function design where its usefulness has, historically, been very limited. Also, problems can occur if the definition being used is wrong or too weak for the application being considered. And, of course, there could be errors in the proofs of security. So the framework should be used with these limitations in mind because a blind adherence to it could lead you astray.

In my opinion the best place to start learning the provable security paradigm (and crypto in general) is the textbook Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell. I really wish this book was out when I was learning crypto because it would have saved me a huge amount of time. The book teaches you all the basics of cryptography while explaining how security definitions work and how to prove various constructions secure. Unlike many mathematically-inclined books it goes over the details of proofs and doesn't just leave everything as an exercise (which can be incredibly frustrating for people who are trying to learn the material alone and without any background). After Katz-Lindell, I would recommend Foundations of Cryptography Vol. 1 and 2 " by Oded Goldreich. These texts, however, are a lot more advanced and you likely won't need the material unless you are doing research.

Learning the Basics

Of course, another crucial step is learning the basics. The simplest thing to do here is to just read Katz-Lindell. In addition you can also watch Jonathan Katz' and Dan Boneh's MOOCS which are here and here , respectively.

Putting it All Together

So you've read Timothy Gowers' blog posts and acquired the basic mathematical concepts, you've read Katz-Lindell and understood the basics of provably security and you've watched the MOOCs so you know all the basic cryptographic primitives and what they are used for. At this point you should be able to read crypto papers and follow along. What you may not be able to do, however, is design and analyze your own crypto protocols.

To make the jump from understanding other people's work to creating your own, I think the only thing you can really do is to formulate your own problem and try to solve do it. Whether you succeed is not important, what matters is that you will be applying everything you learned at once and this will force you to understand how these ideas relate to each other and interact.

While I think it's a good idea to work on your own problems at this stage to gain experience in applying what you've learned, it is very important to keep in mind that you don't know what you're doing yet . In particular, you may have gained a false sense of confidence after reading the books and watching the MOOCs so if you're not careful you'll be headed down the path of crankdom. To avoid this, it is crucial that you get feedback on your ideas from people who are more experienced than you. This is not an option, it is crucial!

But how do you get experts to give you feedback if you don't know any? This is a difficult question that I faced as well at one point. Here's the trick I used. I basically got to the point where I could hold a semi-intelligent conversation with a professional cryptographer. This does not mean that I could impress them. Just that I knew enough of the basic concepts and techniques that I could have a reasonable $10$ minute conversation about some crypto paper I had read. Once I could do this, I tried my luck. For example, I attended crypto seminars at Universities close by. This lead to me talking about research with professors there and eventually starting to work on projects together.

What is important to realize here is that people---especially successful people---are very busy and they just don't have the time to teach you cryptography. If they are professors, then they already have students they are working with and if they work in industry then they have interns and an employer they are committed to. So if you want to learn from them you should have something to offer.

But what can you offer if you are just starting out? Well, if you think about it you have one thing that they don't: namely, time . Remember that these experts are very busy so they probably have a ton of project ideas they would like to work on but that will never see the light of day. What you can offer to them is your time. You can start by implementing their ideas and evaluating them experimentally (this is assuming you have a strong engineering background). By doing this you are providing value to them and, most importantly, you get a chance to demonstrate that you have a good work ethic, that you are committed and that you are easy to work with. On your end, you will learn and internalize their ideas better and put yourself in a position to possibly improve upon them. Once you have a good working relationship and some preliminary ideas on how to improve their work, you are well on your way.

Conclusions

So these were my high-level strategies for learning cryptography. If you can, just get a Ph.D. at a place with a good crypto group (remember that Ph.D.'s in computer science are effectively free). If you really can't do that for some reason, then you can try out the second strategy I outlined. But you should realize that it will be painful.

Good luck!