People often ask me how to get started in cryptography. What's interesting isthat 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 morethan a list of books or papers to read or set of exercises to solve; they'rereally looking for a broader strategy on how to learn the subject. Inthis post I'll discuss some possible strategies.
First, let me stress that I am only considering strategies for learning cryptodesign and theory. Also, what I have in mind when I say "learning crypto" isnot getting to the point of understanding an average paper, but getting to thepoint of generating such papers yourself (or at least the ideas in them). Ifyour end goal is crypto engineering then the strategies may or may not behelpful---I'm not an expert so I can't really say either way ( though I'd liketo think that improving your understanding of how primitives and protocols aredesigned can be helpful).
I should say from the outset that the way I personally got started incryptography is probably one of the worst possible ways to do it. It was highlyinefficient and had a very low probability of success. This was mainly becauseI didn't have the proper background when I started and I didn't have the rightresources at my disposal. These two things are very important and one of twothings is likely to happen if you don't have them: (1) it will take you solong that you'll get fed up and give up; or (2) you'll become a crank (andbelieve me, there are a ton of cranks out there selling crypto products).
When devising and implementing your strategy, you should keep these outcomes inmind 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 aUniversity with a cryptography group. Getting a Ph.D. in some random field likemechanical engineering or biology does not count! If you are interested insymmetric cryptography (i.e., block cipher and hash function design andcryptanalysis), then a good place to start are European Universities since alarge fraction of the experts are there. If you're interested in crypto theorythen the US or Israel. Of course there are strong groups in each areaeverywhere.
If you have found a University and are trying to evaluate the group is, then avery rough sanity check is to look at their publication record. If thisis 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 shouldbe looking for publications at CCS, CHES, IEEE Security and Privacy (also knownas Oakland) and Usenix Security. CRYPTO, Eurocrypt and Asiacrypt are notparticularly good indicators of quality for applied crypto. If this is asymmetric crypto and cryptanalysis group then you should look for papers atFast Software Encryption (FSE) and Selected Areas in Cryptography (SAC).Similarly to applied crypto, CRYPTO, Eurocrypt and Asiacrypt are notnecessarily good indicators of quality in this area.
But you shouldn't get too caught up in this, however. The publication system incryptography is screwed up so you shouldn't necessarily dismiss group $A$ becauseit has less STOC papers than group $B$; or less CCS papers than group $C$. This isjust a very coarse metric that---absent of any other signals---can be used todistinguish between very good groups and very bad ones. Another good thing to checkis where the students that graduate from that group end up. Do they end up withjobs that you would like?
So why is getting a Ph.D. from a good group the best strategy? Simply becauseit is the most efficient way to learn the material. The background needed forcrypto is not part of a traditional education, neither in math nor in computerscience, 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 graduateschool.
In grad school you will have a set of classes carefully chosen and prepared foryou. You'll have an advisor that will guide you through the process, tellingyou what you need to learn, what you don't need to learn, what your weaknessesare, what you need to improve, what problems to work on and the best strategies tosolve those problems. You'll also have fellow students that will help andmotivate you throughout.
Note that for most Ph.D. programs in computer science you don't have to payanything. Your tuition is taken care of by the department or by your advisor'sgrants. In addition, you receive a stipend which takes care of housing, foodetc. So if you're in a position to devote $5$ years of your life to learningcryptography, then I think grad school in a crypto group is by far the beststrategy.
How Not to Do It
So you can't go to grad school or you can but somewhere without a crypto groupand you still really want to learn crypto design and theory. Here is one possiblestrategy---the one I used.
I'll assume you have a standard systems-focused computer science undergraddegree. In my case, for example, I had a strong systems background in undergrad(e.g., compilers, OS, networking, architecture) and a very weak theorybackground (just calculus, intro to algorithms and a linear algebra class sobad no one ever attended). To be brutally honest, this kind of background isuseless for cryptography and if this is the point at which you're at then youhave to understand that you'll be starting from scratch.
There are three things you should be shooting for: (1) developing mathematicalmaturity; $(2)$ learning how to debug; (3) acquiring the basics.
By mathematical maturity, I mean the ability to understand and use basicmathematical language, notation and concepts. It's basically having the rightcontext in place for doing math. Knowing how to parse mathematical statementsand proofs and generally-speaking, knowing how to read between the lines andhow to fill in the missing pieces.
By debugging, what I mean is that you have to get to a point where you canreliably tell whether you have fully understood some idea or not. When you arestarting out and working alone, this is extremely difficult especially for anarea 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 wrongthey are. Many people who are self-taught end up like this so you have to becareful.
The problem with most of the advice given for learning a hard subject is thatthey focus on the third stage; typically by pointing to papers or books. Butpapers 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 anundergraduate education in math. 1
Maturity is probably the skill that takes the longest to acquire. Math andtheoretical areas of computer science are expressed through definitions, theoremsand proofs. A definition is a precise description of some object or process. Atheorem is a precise statement concerning some object or process and a proof isan argument as to why the statement is true. You should be comfortable withthis paradigm because everything you will see further down the line will beexpressed this way. But understanding this paradigm means you'll have to becomfortable 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, theoremstatements and proofs yourself and be able understand why some formulations arebetter 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 intuitiveunderstanding of an idea, but there will be times where your intuitionfails 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 moreimportant---especially when you are starting out.
Most books on cryptography will not help you acquire mathematical maturitybecause it is assumed that the reader has it. If you are coming from a purelysystems 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 worsesince mathematicians learn this stuff very early on.
So what can you do? The approach I took was to just read everything I couldfind in math, theoretical computer science and cryptography. Once in a while, Iwould get lucky and find a paper with a decent explanation of some basicconcept (e.g., some basic probability argument or a slightly more detailedproof structure) but most of the time I had to reconstruct the missing thepieces and context on my own.
Obviously, this is easy to do when you have the basics but it is incrediblydifficult and frustrating when you don't. As you can imagine it took foreverto fill in the gaps in my knowledge. Therefore, the ideal approach would beto find a book or lecture notes that focus on this stuff. And---luckily foryou---Timothy Gowers has written an excellent series of blog posts on thesevery things so you should read them:
- Basic Logic
- Functions
- Permutations
- Definitions
- Equivalence relations
Debugging
Being able to detect whether you've made a mistake is an important and difficultskill to acquire in any subject. This is exacerbated in security andcryptography 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 formulatesa security definition that captures the security properties/guarantees that areexpected from the system. Then, one describes a cryptographic scheme/protocolfor the problem at hand. Finally, one proves that the scheme/protocol satisfiesthe security definition (usually, under some assumption).
The provable security paradigm originated in the 80s' and has been used eversince 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 isa great debugging tool. When trying to prove the security of your primitive, youwill sometimes find that the proof will not go through for some reason and, moreoften than not, it is because of a subtle weakness in your protocol that you didnot pick up when first designing it.
I want to stress that the provable security paradigm is not foolproof and thatit has its limits. For example, there are entire areas of cryptography likeblock cipher and hash function design where its usefulness has, historically,been very limited. Also, problems can occur if the definition being used iswrong or too weak for the application being considered. And, of course, therecould be errors in the proofs of security. So the framework should be usedwith these limitations in mind because a blind adherence to it could lead youastray.
In my opinion the best place to start learning the provable security paradigm(and crypto in general) is the textbookIntroduction to Modern Cryptographyby Jonathan Katz and Yehuda Lindell. I really wish this book was out when I waslearning crypto because it would have saved me a huge amount of time. The bookteaches you all the basics of cryptography while explaining how securitydefinitions work and how to prove various constructions secure. Unlike manymathematically-inclined books it goes over the details of proofs and doesn'tjust leave everything as an exercise (which can be incredibly frustrating forpeople who are trying to learn the material alone and without any background).After Katz-Lindell, I would recommend Foundations of Cryptography Vol.1 and2"by Oded Goldreich. These texts, however, are a lot more advanced and youlikely 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 dohere is to just read Katz-Lindell. In addition you can also watch Jonathan Katz' andDan Boneh's MOOCS which arehere andhere, respectively.
Putting it All Together
So you've read Timothy Gowers' blog posts and acquired the basic mathematicalconcepts, you've read Katz-Lindell and understood the basics of provablysecurity and you've watched the MOOCs so you know all the basic cryptographicprimitives and what they are used for. At this point you should be able to readcrypto papers and follow along. What you may not be able to do, however, isdesign and analyze your own crypto protocols.
To make the jump from understanding other people's work to creating your own, Ithink the only thing you can really do is to formulate your own problem and try tosolve do it. Whether you succeed is not important, what matters is that you willbe applying everything you learned at once and this will force you to understand howthese ideas relate to each other and interact.
While I think it's a good idea to work on your own problems at this stage togain 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 andwatching the MOOCs so if you're not careful you'll be headed down thepath of crankdom. To avoid this, it is crucial that you get feedback on yourideas from people who are more experienced than you. This is not an option, it iscrucial! 2
But how do you get experts to give you feedback if you don't know any? This is adifficult question that I faced as well at one point. Here's the trick I used. Ibasically got to the point where I could hold a semi-intelligent conversationwith 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 areasonable $10$ minute conversation about some crypto paper I had read. Once Icould do this, I tried my luck. For example, I attended crypto seminars atUniversities close by. This lead to me talking about research with professorsthere and eventually starting to work on projects together.
What is important to realize here is that people---especially successfulpeople---are very busy and they just don't have the time to teach youcryptography. If they are professors, then they already have students they areworking with and if they work in industry then they have interns and anemployer they are committed to. So if you want to learn from them you shouldhave something to offer.
But what can you offer if you are just starting out? Well, if you think aboutit you have one thing that they don't: namely, time. Remember that theseexperts are very busy so they probably have a ton of project ideas they wouldlike to work on but that will never see the light of day. What you can offerto them is your time. You can start by implementing their ideas and evaluatingthem experimentally (this is assuming you have a strong engineeringbackground). By doing this you are providing value to them and, mostimportantly, 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, youwill learn and internalize their ideas better and put yourself in a position topossibly improve upon them. Once you have a good working relationship and somepreliminary 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 incomputer science are effectively free). If you really can't do that for somereason, then you can try out the second strategy I outlined. But you shouldrealize that it will be painful.
Good luck!
- A math education will teach you the building blocks from which most cryptographic protocols are built (e.g., number theory, algebra etc.) but it won't teach you specifically how to design crypto primitives and protocols or how to understand and analyze their security. [return]
- At one point when I was just starting to learn crypto I wrote up some ideas I had. Someone I knew agreed to do an introduction with a well-known cryptographer so I could send him my ideas. After reading my ideas, he (very politely) told me that what I was doing made no sense, explained why and then (again very politely) proceeded to explain why working together would be too difficult given the stage at which I was. This was one (by far) of the most important stages in my development. This small feedback that he provided made me realize that I had acquired a false sense of confidence and that I still had a huge amount of work to do! Looking back, this was invaluable and I'm grateful to him to this day. [return]
Tags// Learning,
More Reading
Newer//Microsoft Research SVC and Applied Theory
Older// Microsoft Research Internships