How I became a cryptographer

One of the questions that keeps on appearing over and over in Reddit’s /r/crypto is how to become a cryptographer.  For example this and this and this and this and this.

I often reply to these in comments. But given that the questions keep coming up, I thought it would be good to write up something more complete that I could reference back to. In doing so, I hope I can pass on some valuable tips that I learned the hard way on what it takes to “make it.”

When I say “make it”, I’m referring to being able to make a career as a cryptographer and nothing more. This blog assumes you understand what I mean by “cryptographer”: see Schneier’s article from 1999.  In short, I am showing the path I went down in order to be able to make a living publishing research papers on cryptography, which is not the same as being a practitioner using cryptography.

Often people replying to “how to become a cryptographer” say get a PhD in cryptography and publish lots of papers. That does not answer the question of “how do I qualify myself to get a PhD?” or “How do I learn to think like a researcher?” or “How do I do research?” Nor does it tell how to do significant research. I hope my blog provides some guidance on these questions.

I myself consider that I made it to the level of mediocrity as a cryptographic researcher. I certainly was no star. But I also started late in the game in terms of developing the way of thinking like a researcher. I believe most of the others had the tendency towards mathematical thinking from a young age. Because of that, I had a lot of catching up to do to compete with many from the field. If you’re reading this blog, then you might be like I was, and thus I hope it provides some helpful tips to you that I had to learn the hard way.

Here are what I believe are the 7 magic ingredients to becoming a cryptographer (in no particular order):

• You need to be a brilliant mathematician (amended advice given here).

• You need to be very strong in algorithms, including development and analysis.

• You need to work your tail off.

• You need to be creative in problem solving.

• You need to be passionate about the field you are in.

• You need to surround yourself with experts in the field.

• You need a bit of luck (but luck happens when preparation meets opportunity!)

Now I tell my story.

My mischievous youth

I believe that those who have achieved a far-reaching life goal can look back at points from their early ages that contributed to where they are today, so this is where I start.

One trait I had that really contributed to my eventual career was my passion for creative puzzle solving. I personally was not so keen on listening to others (which is not good, by the way): instead I spent many hours trying to find solutions myself. In the early days, this manifested in examples like coming up with my own way to solve the Rubik’s cube, never reading the book.

I guess around 10 years old, I started using a computer and learning to program it. It spent many hours, not shy to sacrifice a whole weekend, to make computer games. By the time I got my first 300 baud dial-up modem, I learned about bulletin board systems (BBSs) where nerds like me developed online social lives. For those who don’t know about BBSs, think of it as like a stone-age Facebook.

It didn’t take long before thoughts of mischief on BBSs popped into my head. I spent many hours reading source code of the main BBS that Commodore 64 users were using and thinking about how I could do stuff that the system was not intended to do. I had particular interest in destructive actions solely for the purpose of childhood entertainment. My specialty was crashing (i.e. Denial of service) BBSs. Yes, I was extremely immature.

By age of 16, I was lucky to have access to a local free-to-use Unix system that I could dial into. It didn’t take long before I was exploring the cool /etc/passwd file. A friend of mine had discovered the algorithm that created the password hashes, and I spent many, many hours with no success in trying to invert that algorithm. This was my first exposure to modern cryptography, though at the time I did not know that I was trying to invert a hash function based upon the Data Encryption Standard (DES).

Being exposed to a Unix system and the C programming language 2 years before starting University gave me a head start. Knowing how to program and hack also made me a good candidate for becoming a cryptographer. But I was lacking what may be the most important ingredient: I was not a brilliant mathematician. Don’t get me wrong: I was decent at mathematics, but by no means brilliant. Maybe I was in the top 15% in my class. That’s nothing compared to most cryptographers who were surely the #1 in their school and beyond. For example, looking at the list of Putnam Fellows (top undergraduate mathematicians in the USA and beyond), one will see several cryptographers on the list.

University learning: changing the way I think

Because I was lucky enough to have my parents pay for my University education in America, I was free to commit a lot of time to learning. I wanted my parents to know that their money was not being wasted, so that drove me to work hard. Extremely hard work.

At the same time, I was going through some phase of not trusting anything. This was back in the Cold War days, when we were told that Russian people are evil and they all wanted to kill us and eat our brains. I was not that gullible, and the skepticism I had developed towards authoritative sources of information ended up being the essential ingredient in changing my way of thinking towards the direction of a researcher.

I did pretty well in my classes, though I often came up with reasons for not believing what they were teaching me, especially physics. I looked to come up with an excuse on why it could be wrong. Can the science of physics be wrong? In order to prove something about reality, you need to make assumptions about reality, and that’s the part that I could always question. Footnote: I no longer take such an extreme skepticism towards everything.

After dismissing physics, next came mathematics. How can I show it is wrong? This is an interesting question, because I like many people “learned” mathematics by “memorising the formula” and using it to solve problems. But if I am questioning everything, I can’t take the approach. Instead, I need to disprove the formula. This became a whole way of thinking for me.

When you go to University, you get lectures that you take notes from and a book to read. Which one am I supposed to learn from? I don’t know. I’ll try both.

In the end, I could not make any sense out of my notes, but I could learn from reading the book. The book gives you so much more information that can be packed into a one hour lecture, but the consequence is that you need to spend a lot more time learning. And if you want to disprove the book, you have to spend even more time!

So there I went: reading every single sentence and formula from the book, one-by-one, and trying to disprove it. And absolutely not going to the next one until I am 100% convinced that the sentence or formula is logically correct. To my surprise, I never came across a single thing I could disprove (other than perhaps small mistakes that were easy to correct). And this is what attracted me to mathematics, which ultimately provided me with the thought process I needed to become a cryptographer.

This I believe illustrates an important difference between how most people learn versus how people who end up becoming cryptographers/mathematicians learn. Most people trust the authoritative source. If you want to be a cryptographer, you cannot have that mindset. Instead, you need to question everything and confirm that everything you are being told is true.

Understand why. We cryptographers all the time are seeing new ciphers with miraculous security claims. If we were to not question things like we do, then there would be a whole lot of snakeoil used in the real world. When a mathematician reviews a proof, he looks for anyway that it may be incorrect – especially edge cases come into play. Similarly, if you can find any exception to a proof or claim of security for a cipher (especially edge cases come into play), that could be the key to breaking it. Sometimes finding flaws in security proofs have huge implications even if the flaw does not translate into an immediate break of the construct.

I later learned that you need to go beyond that: you have to be able to prove the same thing you are reading, not just check that it is true. This of course is an even bigger time commitment, but you eventually learn to figure out the key points of the proof and then reconstruct the rest of it yourself.

When I did homework, I went to the library. Before I started, I would look around and carefully remember anybody I could see around me. After that I would start doing homework, giving full attention to my homework until it was all done. Then, I would look around to see if there is anybody still there that got there before me: my rule was nobody can study harder than me. If I found somebody, it meant that I needed to keep on studying. If there was no homework left to do, find a book to read on my current subject and learn a lot more than what the notes and the other kids in the class are learning.

For some classes, I really enjoyed this. For example, in discrete mathematics / combinatorics, I went to great extents to try to find problems I could not solve. I had mastered the class textbook, which I loved, but I was able to find some very old books in the library that were 100% dedicated to tricky combinatorial problems, and I worked out every one of them until I got to the point that I could solve just about anything thrown at me.

As you can see, I worked my tail off at the University and changed my way of thinking. I did not know it at the time, but this was actually my “catch up” time for getting my mind thinking the way the brilliant mathematicians who end up becoming cryptographers think.

I ended up with a double degree in mathematics and computer science. I did quite well, getting almost all A marks in mathematics and computer science, but not always the same success in other subjects. In my third year of University, I did a graduate level class in cryptography, which I loved, and decided that I wanted to do as a career. I just didn’t know how, but I did know that graduate school is probably the right direction forward.

Graduate school: learning to do research

My parents were generous enough to pay for my undergraduate education and expenses, but now that I was all grown up, it was time for me to cover myself.

I tried very hard to get scholarships to help pay for my graduate school education. But at the end of the day, I was competing with students who already have patents, publications, and the like. Also, I was against all-A students and students that have scored perfect on their GRE. How could I possibly compete? The answer was that I needed to earn my way by being a teaching assistant (TA). Being a TA is a huge time commitment, which takes away from the learning that I really wanted to do, but it was the only way I could go forward.

I got accepted to some decent Universities, but top schools like MIT and Stanford were quick to turn me down. Of the ones that accepted me and offered me enough income from TA to pay my way, I decided to go to University of Wisconsin-Milwaukee Computer Science Department, which had a few cryptography professors. I was considered the star student of the time, but in retrospect, this guy turned out to far out-shine me.

I spent two years there taking classes and doing research. My research focus was number theory, particularly integer factorisation. Although I did well in mathematics as an undergrad student, it seems that one really needs to have a lot deeper mathematics background to do innovative research in factoring, so I mainly focused on implementation.

At that time, Arjen Lenstra at Bellcore was in his early days of what would be his long streak of smashing integer factoring records. I loved his research, but I also viewed him as my competitor: if I am going to “make it”, I need to beat him.

Just as an undergrad, I was working my tail off. I was 100% committed to intellectual development. When I wasn’t doing TA duties, class work, or research, I was reading the Usenix groups such as sci.crypt and sci.math, and contributing to discussions. I also spent a lot of time breaking amateur ciphers that were posted on sci.crypt.

After 2 years, I was completing my Masters Degree and was exhausted from all the hard work. I decided that I needed to take a whole summer break just to gather myself. But fortune had another plan for me.

I received an email from Arjen Lenstra. This was not long after he had factored RSA-129, which got international press. Arjen was looking for a summer intern to work with at Bellcore.

There I was: exhausted, feeling as if I had spent 6 years fighting Mike Tyson, needing a rest, and then getting an email from my “competitor” asking if I wanted to work with him. What was I to do?

Thankfully, my parents and friends had set my mind straight. I was wanting to turn it down, but they said I would be absolutely crazy to do it, and they were right. I took the opportunity, which turned out to be the single most important decision in my career. Let me be 100% unambiguous: if I would have declined this opportunity, I would never had made it as a researcher. Luck definitely played a role for me.

One of the most important things I learned from Arjen is that when I develop new algorithms, I need to prove that they are correct. This is obvious to a researcher, but it was not obvious to me. I had ways of solving problems that he wanted me to work on, but he said he wanted proofs before I went ahead and implemented them. And so I did.

In all honesty, I didn’t feel like I did great working for him that internship, but I had enough background in what he wanted me to work on to make me succeed. As I said, I was exhausted from all the studying and TA duties, so I did not commit 100% like I had done for University study. I also had planned to take my time off to gather myself at the end of the 3 month internship.

To my surprise, as the internship came to an end, he asked what I was doing after it. I said “nothing.” He then asked why not stay working there until the end of the year. Hmmm, the pay is good, the experience is great, and what he wants me to work on is exactly what I want to work on. I’ll take it.

I spent the next approximately 5 months working on a project with Arjen that really excited me. We were using the MasPar massively parallel computer to implement fast linear algebra algorithms to solve factoring matrices. We ended up writing a research paper on it, but it never got submitted anywhere. This was my fault: I was too busy to finish it off, and I thought it was research that nobody would be interested in. I was wrong.

During that time, I got back into the mindset of a researcher and I seem to have forgotten that I needed time to gather myself. I decided that having a Masters in Computer Science was not really what I needed: instead I needed an advanced degree in Mathematics. And I was 100% certain that I wanted to do that working for Carl Pomerance at the University of Georgia.

Carl was a well known star in Number Theory. He along with Andrew Granville and Red Alford just completed a proof that there are infinitely many Carmichael numbers, which excited me. Carl was also well known for factoring. I didn’t realise it at the time, but one of the reasons why everybody knew Carl is because he wrote his research so well that even an idiot like me could understand it. Not many mathematicians have that skill.

I thought I would be able to comfortably get into the University of Georgia, but I was wrong. On paper, I was borderline to get into their Masters program, and especially, getting a TA job was going to be tough.

Completely out of character for me, I decided to make a 10 hour drive to Georgia to meet with Carl and other people at the University, and convince them that they should accept me as a graduate student. I wonder to this day if they ever had anybody else approach them like that. I went there, talked to a number of Professors, told them about who I am and what I wanted to do. If nothing else, they saw the passion for mathematics and research in my eyes, and combining that with a letter of recommendation from Arjen, they decided to give me a shot. I got accepted and was offered a TA position.

Truthfully, I don’t know if they really believed that I would make it, and rightfully so. I did not know about the level of competition I was going to find at this University, but as before, I was able to make up the difference by extremely hard work. This was also the time that I learned that checking the proofs is not enough: you need to be able to prove everything in the book yourself.

I surprised a lot of people and eventually they accepted me as a PhD student. Carl Pomerance and others really believed in me. But eventually, 8 years of intense University studying had clobbered me. I was beat and financially in debt, and I really needed a break. Carl tried hard to convince me to go through with the PhD, but I just couldn’t find the drive any longer. I bailed out with a Masters degree.

At this point I had a double Bachelors degree in Mathematics and Computer Science, a Masters degree in computer science, a Masters degree in Mathematics, and letters of recommendations from big shots Arjen Lenstra (pretty much the top computational number theorist ever) and Carl Pomerance (big shot analytical number theorist). Suddenly, how I looked on paper was representative of how good I considered myself to be. And with that, I got a position in industry as a research associate that I believe I deserved, working for RSA Labs at RSA Data Security.

The only catch is, even though I did research to get my Masters degrees, my research was not particularly innovative. So I can’t call myself a researcher yet.

Getting my first publications

It took me a bit of luck to upgrade my skills and get myself where I needed to be in University and graduate school, but at this point I believe that I truly was the best person for the position I took at RSA Labs. Having said that, what an amazing opportunity it was to see minds like Ron Rivest and Yiqun Lisa Yin in action.

It happened to be a convenient time to work there, as there was a call for an Advanced Encryption Standard and RSA Labs had one of the top candidates: RC6.

Ultimately, I had no contribution making it to the final design of RC6, but I was able to make contributions to the analysis. My tendency to disbelieve anything that lacked a proof was instrumental for me in attempts to check the heuristic analyses that the team did to understand the security. It turned out that the heuristic analyses didn’t hold for some simplified variants of RC6, which resulted in my first publication, with Ronald Rivest, Matt Robshaw, and Yiqun Lisa Yin as coauthors.

It was not that difficult to get this result.  I wrote a program to try to verify heuristic claims.  I saw that those claims were not always correct.  I spent time understanding why the claims do not work via debugging and analysis, and worked with my colleagues to develop the analysis further.  Then formal proofs, write-up, and publication.

I did a fair amount of work with Yiqun Lisa Yin, who helped me get a few other publications coauthored with her. She is a brilliant mind and knew where the research community was going. She had the great ideas and I helped where I could.

Despite my success in getting publications, I felt: (1) the results are not significant enough to make me feel as I have “made it” as a researcher, and (2) except in the one publication above, the main ideas were largely coming from other people rather than myself.

Getting significant research results

The position at RSA Labs lasted about 2 years, at which time the company who bought out RSA decided that research in cryptography was not so important, so cut off the West coast research arm.

For a number of years after that, I went back and forth between academia and industry, seeking another position like I had at RSA Labs. I wanted to be do research but also develop software. It turned out that such positions are extremely rare.

I had a couple positions that are normally for post Doctorate students despite not having a Doctorate. One of those was at Macquarie University, with the aim of doing research in Number Theory.

Unfortunately, I did not have strong enough background to do significant research in Number Theory, at least I didn’t think so. I did get a few crypto publications during this time, but I felt they were fairly small results. Towards the end of the appointment, I was ready to give up.

(Side note: I actually did my PhD while at the same time holding this PostDoc position).

It was my office-mate, Ron Steinfeld, who suggested that we look at hash functions. He had some ideas that I was happy to work on him with.

Somehow, I got distracted and started thinking about a hash function built by multiplying small primes together. I wrote a simple equation on the whiteboard and looked at it. I then noticed that if there is a collision, something remarkable happens.

I turned away and thought, “no I need to get back to number theory research.” Gratefully, the little man in my head shook my brain and screamed: “What’s the matter with you, idiot! There’s something interesting here!” So I went back to the equation, thought about it more, and then convinced myself that there is opportunity here. I showed it to Ron, and he said this looks like a breakthrough.

Ron helped me formalise it and justify its significance, and we wrote it up in pretty good detail. Igor Shparlinski helped us in an essential analysis part, but he said he didn’t think his contributions were significant enough to coauthor. We then showed it to Arjen, who had an idea to make it faster and helped the overall writeup.

Finally, I had my breakthrough. The VSH hash function was published in Eurocrypt. The paper happened just after the Wang et al were breaking all the practical hash functions. I had solved the right problem, in the right way, at the right time. Or at least so I had thought.

Another significant area I worked on was HMAC. Given that the hash functions are broke, what are the implications to it? Yiqun led this. My main contribution was coming up with practical algorithms to attack HMAC and NMAC given hash collisions, which was significant to the paper. So this was my second significant research result.

Finally, I feel like I had made it as a cryptography researcher. Finally I started having confidence that I could make a career doing this. Ironically, I decided to not do so.

Additional tips for those aiming to become cryptographers

I would like to think I have learned a thing or two about research in all these years of effort. So here is the advice I pass on to those who are just making the journey.

The number one advice is read Richard Hamming’s advice on how to do great research. I first discovered this while doing my “PostDoc” research at Macquarie University. I must have read this at least 10 times thereafter. You need to know where the field is going to make significant contributions. If you don’t work on the right problems, you’re not going to have an impact. Surrounding yourself by experts in the field will help guide you in making an impact. Don’t be afraid of going after the big problems.

Another point from Hamming is selling your research. He is so right. When I first got publications, I considered the writeup the boring part: I had solved a problem, now I need to waste all this time writing it up rather than go out and solve more problems? Absolutely the wrong attitude. Think about the people you look up to as researchers. You might have names like Dan Boneh, Adi Shamir, etc…. If your list is anything like mine, you may notice that they are great communicators. They write well and they present their research well. If you can clearly explain and motivate the problem you are trying to solve, it will not only attract others to your research, but it will also help you better understand the value of your research and the interesting directions you can go.

Doing research is frustrating. One of the things that threw me off is that although I was very good at a lot of things, I just did not have the mathematical depth of many people in the field. How could I do compete with them?

It wasn’t until VSH that it dawned upon me that you don’t have to be the greatest mathematical mind to make an impact. Think of great impacts like RSA: it was just a coincidence that it was invented by some of the best cryptographers ever, but mathematically it really is very simple. Another example is Shamir Secret Sharing: such a simple concept with great impact: it is only a coincidence that it was invented by the greatest cryptographer ever! My point is that don’t be intimidated like I was just because other people know more – often simple ideas have the biggest impact. Try a lot of ideas, and be creative and persistent.

It really helps a lot to master some mathematical tools. For me, smoothness was what helped me, and it had only been used minimally for constructive purposes in cryptography before.

Many times I thought to myself “I really need to master lattices”, but then later dismissed it: “I’m too late: all the low hanging fruit is gone.” I was so wrong: it was never too late!

Why I left cryptography

If there is interest, in a future blog I will write about why I left cryptography.