11/Nov2014
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. 1
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:
- Basic Logic
- And & Or
- Not
- Implies
- Quantifiers
- Negation
- Converse and contrapositive
- Handling variables
- Summary
- Functions
- Injections, surjections, etc.
- Co-domains, ranges, images
- Permutations
- Definitions
- Definitions
- Alternative definitions
- 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! 2
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!