Quantum computing is a completely different paradigm from classical computing, where weird quantum properties are combined with traditional boolean logic to create something entirely new. There has long been much doubt about whether it was even possible to build one large enough to solve practical problems. But when something is labeled "impossible", of course many physicists, engineers, and mathematicians eagerly respond with "Hold my beer!". QCs have an immense potential to make a global impact (for the better!) by solving some of the world's most difficult computational problems, but they would also crush the math problems underpinning much of today's internet security, presenting an unprecedented challenge to cryptography researchers to develop and standardize new quantum-resistant primitives for post-quantum internet.

We are mathematicians trained in crypto at NSA, and we worked there for over 10 years. For the past year or so we've been at a small crypto sw/hw company specializing in working on a post-quantum research effort, and we've been reading a broad spectrum of the current research. We have a few other co-workers that will likely also chime in at some point.

Our backgrounds: Rino (/u/rabinabo) is originally from Miami, FL, and of Cuban descent. He went to MIT for a Bachelor's in math, then UCSD for his PhD in math. He started at NSA with little programming experience, but he quickly learned over his 11 years there, obtaining a Master's in Computer Science at the Hopkins night school. Now he works at a small company on this post-quantum research.

John (/u/john31415926) graduated summa cum laude from the University of Pennsylvania with a B.A. in Mathematics. After graduation, he went to work for the NSA as an applied research mathematician. He spent 10 years doing cryptanalysis of things. He currently works as a consultant doing crypto development in the cable industry. His favorite editor is Emacs and favorite language is Python.

Disclaimer: We are bound by lifetime obligations, so expect very limited responses about our time at NSA unless you're willing to wait a few weeks for a response from pre-pub review (seriously, I'm joking, we don't want to go through that hassle).


Edit to add: Thanks for all the great questions, everyone! We're both pretty beat, and besides, our boss told us to get some work done! :-) If I have a little time later, I'll try to post a few more answers.

I'm sorry we missed some of the higher ranked questions, but I'll try to post answers to most of the questions. Just know that it may take me a while to get to them. Seriously, you guys are taking a toll on my daily dosage of cat gifs.

Comments: 794 • Responses: 43  • Date: 

useafterfree784 karma

I read recently that NSA has distanced itself from lattice based crypto. I can't find the article now though of course. Is this true? Can you say why? What approaches do you think will be the future of quantum-resistant crypto?


What do you guys think of the importance of provably secure schemes? Will they ever be practical and used in real world applications?

Finally make your response an even number of characters if Diffie-Hellman has been practically broken, odd if it has not. Thank you.

rabinabo99 karma

Sorry for the late response. This was one of the more interesting questions (except for that last request), so we should have responded yesterday. I'm not even going to bother counting the number of characters.

I don't think I've seen anything from the agency indicating disfavor with any of the post-quantum schemes, actually, but as you know, they're rather tight-lipped. Although, the NSA did make [an announcement](tinyurl.com/SuiteB) that recommended to start moving towards post-quantum crypto. They also specifically suggested that ellictic curve cryptography is particularly vulnerable to quantum computers, and there's even a paper that tries to guess at the reasons behind that statement.

As a mathematician, I think provable security should definitely a worthy goal, especially when proofs in this area are hard to come by. Take RSA, which is almost mentioned as difficult to break as factoring. We only know for sure that breaking RSA is at most as hard as factoring, and there are indications that breaking RSA may be easier. So yes, I think that it worthwhile to have a proof that the security of a crypto scheme can be reduced to a long-standing problem. You have to be careful about how tight your bounds are, though, as it's possible for them to be so loose as to render your proofs useless.

One aspect with lattice based crypto that I think is a selling point is the worst-case hardness, which says that breaking the crypto in any case implies that you can break the other long-standing problem in the worst case. The way I think of it is that it gives some assurance that there isn't some broad class of special cases that the crypto has to avoid, which has happened many times with RSA, Diffie-Hellman, and ECC.

As for practicality, Google ran a trial run of New Hope on Canary.

turnipheadscarecrow128 karma

(Originally asked in /r/math)

Do you think the NSA is good? When you were working there, were you happy with the impact you were having in the world? We know that the NSA is spying on everyone, we know it grossly oversteps its mandate. You might have to pretend when working at the NSA like you don't know what I'm talking about, but now that you're out, I assume you can be more honest with yourselves.

The math is doubtlessly interesting, and there are many selfish reasons to want to work at the NSA. But I want to know, if you do some soul-searching, do you think you did the right thing for the world by working at the NSA?

rabinabo201 karma

I will not make any comment on the leaks, other than to say what was leaked was specifically chosen by the leakers. For what purpose, I cannot say, but it was definitely not to improve NSA's public relations.

More relevant to me are what the leaks have failed to reveal. The NSA has a very broad mission, and there is a lot of great work being done there that is not represented in the leaks. I worked in Information Assurance for most of my NSA career, and at the end of the day I don't feel bad in any way about my work at the agency. I can't really say anything more than that.

baldr83100 karma

You might have to pretend when working at the NSA like you don't know what I'm talking about, but now that you're out, I assume you can be more honest with yourselves.

There's a respectful and level-headed way to ask this type of question. This is not that way.

edit: I was getting some downvotes, so I'll offer up a rewording (that they could actually potentially reply to):

The NSA has an impressive history of work but is often criticized for having much too broad surveillance authority. Have you ever had qualms about doing work for an organization that is large and powerful and viewed by many to infringe on privacy?

rabinabo90 karma

I didn't really take any offense at the original question, except that I disagree with all the things that he says that "we know".

turnipheadscarecrow51 karma

The government has told their employees that they can't look at leaks even if the general population can. That's what I was referring to. I assumed the NSA has also told their employees to not look at the Snowden leaks. It would be weird if the employees actually were unaware of the leaks, so I assume they might have to lie about their knowledge of them.

rabinabo105 karma

This is absolutely true. The publication of classified information does not change the classification, so looking at these documents on my home computer would technically be a security violation. Believe me, NSA employees are aware of the leaks. Many would also love to respond to these allegations, but they are heavily restricted from doing so. Any comment about the agency that I'd want to make would have to be approved by the agency before publication, part of my lifetime obligation after leaving the agency.

spanishgum99 karma

HI! I made a comment on your post in /r/crypto yesterday, which stirred up some discussion on the differences between a quantam computer vs. a quantam annealer.

How are these two used differently? Do they have different application domains? Is one more powerful than the other?

I have degrees in Pure Math and CS, but have not been exposed to much quantam physics outside of a Modern Physics course back in (math) undergrad. Do you think it will be difficult for me to break into this field of research?

rabinabo117 karma

I think you probably have enough knowledge already to get started. The nice thing about quantum computing is that the physics has been abstracted in such a way that you only need to understand a few basic fundamental quantum properties that are being applied. In computer science, it's like saying that you don't need to understand the physics of semiconductors to write code. I read some of the classic Chuang-Nielsen text back in grad school.

Frankly, I don't know all that much specifically about the quantum annealing approach, but it is definitely far removed from the models that most quantum computing algorithms are based on, that I'm more familiar with. This paper, for example, shows that you could use quantum annealing to factor. One of the key pieces of Shor's algorithm is that it can be efficiently implemented using the quantum fourier transform, and my guess is that the annealing approach is not nearly as efficient, by the time you translate between models.

spanishgum27 karma

Thank you for the response, and the links! I will look into these. Your note about the abstractions is encouraging. The thought of writing software in this domain is pretty overwhelming. I suppose through teamwork with physicists and mathematicians that the barriers of entry get looser.

rabinabo55 karma

Oh, I just remembered about open-source quantum computing simulators that are around, like LIQUi|>. It's really fun to play around with.

MPREVE93 karma

a: Is any of this wrong? My vague understanding is this: most or all current cryptography in use is based around hidden subgroup problems, such as factoring. These problems are suspected to be intermediate between P and NP, and they're particularly susceptible to a quantum computer framework via Shor's algorithm.

b. So, is the main goal of post-quantum crypto to discover a more robust kind of problem that wouldn't be weaker to the QC framework?

c. If this is still an outstanding problem-- why? It seems like many NP-complete problems could work.

d. What are the most important open problems in the field?

john3141592658 karma

From an intuitive view, NP-complete problems don't generically work because it seems like you need some extra structure like commutativity or a trapdoor to make a key-agreement or key-encryption scheme. When you add the extra structure, you may end up in a subclass that is weaker than expected. Historically, this has happened quite often, knapsack problems being one example.

The other issue is asymptotic versus concrete security. You have to fix parameters for a crypto scheme in such a way that it is efficient, both in terms of time and space. Then, you have to carefully cost how long it will take various algorithms to solve the problem. For example, SAT is the canonical NP-complete problem, but there has been a lot of active research on better algorithms and heuristics and also faster implementations.

Right now, there are open questions on both the asymptotic security of new assumptions, eg, the supersingular isogeny scheme (an earlier non-supersingular variant was broken) and also the concrete parameter choices, eg, lattice dimensions.

djao169 karma

Hi, I'm the inventor of supersingular isogeny Diffie-Hellman, and also /u/rabinabo's old college roommate. I think it's important to point out that the same person who broke the non-supersingular variant (i.e., me) also designed the supersingular variant specifically to be immune to the weaknesses that affected the old non-supersingular variant. So there is actually reason to believe that that the security of the non-supersingular variant does not affect that of the supersingular variant. Of course the security of this or any other cryptosystem is still an open assumption, and it is up to the community to compile evidence for security and decide which schemes to trust.

rabinabo113 karma

Thanks, David! It's an incredible challenge to design a post-quantum scheme imo. It's such a delicate balance between complexity, key sizes, and immunity from attack by both classical and (not yet existent) quantum computers!

It was really funny the day I started at my company, when I was given a few papers to read, and lo and behold, one of the main ones was authored by my college roommate!

ophanin65 karma

Hi! With mentioning that Quantum Computers are coming up and their ability to help solve computational problems, how far would you guess that we are away from an actual functioning quantum computer? I feel like I see a wikipedia link or similar for it every year or so, and it's one of those "Always 5 years away" kind of developments.

rabinabo108 karma

That's not really my field, and even then, it's difficult to guess. I think the rate of progress is accelerating, with Google looking to move from 6 qubits to 49 in the next year. At that point, it can start to answer questions that classical computers aren't capable of answering (i.e. quantum supremacy). I believe that is also close to where you can start solving some interesting problems in quantum simulation. If it can be used to improve the efficiency of the Haber process to make fertilizer even a little, for example, it would have global-scale impact, as it takes up 1-2% of yearly global energy usage.

Wittyandpithy28 karma

The way someone on an AMA explained quantum computing is that they are very dumb computers, except for doing some very specific tasks.

Could you explain how quantum computing renders encryption obsolete?

netsecwarrior33 karma

(I'm not OP, but...)

Quantum computers can perform large numbers of operations simultaneously.

One of the simplest ways to break encryption is through brute force. Pick an initial key, try to decrypt the message, see if the result makes sense. Try another key, and another, until all the keys have been tried. The defense against this is that encryption keys are large - usually 2128 bits or more. That means a brute force attack would require so much computing power and time, that it is impractical.

Quantum computers could theoretically try all 2128 keys at once. A bit in a classical computer and be 0 or 1. A qubit in a quantum computer can be in an uncollapsed state where it's either 0 or 1. If you have 128-qubits input, which is uncollapsed, theoretically a quantum computer can perform all 2128 operations simultaneously.

This is a bit of an over-simplification. In particular, for breaking symmetric ciphers, actual techniques won't work this well. But it is thought that the common public key algorithms (like RSA and Diffie-Helman) could be broken.

rabinabo44 karma

That is the power of superposition! Yes, you can create quantum states with the outputs of all those 2128 keys, but in order to look at any of those values, you have to disturb that quantum state, collapsing it. You basically get to make a coin flip on all those 2128 inputs and get to look at just one output, and then you'd have to create that initial state again, if you didn't get the answer you wanted.

Quantum algorithms have to change the odds in their favor, like gaming the roulette wheel to make it more likely to give you the answer you want. In Shor's algorithm, you change the odds so that your roulette wheel spin is more likely to give a result that will factor n.

polks1326 karma

Hey guys, thanks for doing the AMA!

I'm a graduate student studying algebraic number theory with the ultimate goal of working on cryptographic problems, although I'm not sure in what capacity: private, public, or academic. Great to see some successful people in the field! I have a couple of logistical questions regarding your time working for the NSA and generally in encryption.

  1. I'm not sure you can answer this one, but I figure it's worth a shot. I have a friend (a fellow mathematician) who worked at the NSA as an intern a while back and mentioned that in his experience there is far less intrusion in civilian data than people make out to be in the news. Do you think the NSA is unfairly represented in the media? To that end, what are your opinions on Edward Snowden's actions?

  2. Could you talk a little bit about your experience in private industry encryption? The thing I love about cryptography is its immediate applications of pure math to something so relevant today, but when I look for encryption work that doesn't require a doctorate in mathematics, I generally see very little pure math in the job description. What kind of math do you use in your work? Similarly, what kind of math did you use in the NSA?

  3. What's your favorite prime number and why?

Thanks again guys!

rabinabo46 karma

That's great! We were talking about the continued relevance of algebraic number theory, so I'll point you to this fairly recent paper as proof. :-)

  1. I'd LOVE to answer this, but it's very tricky to give you any straight answers.
  2. I think there's increasingly more sophisticated math involved, as the field looks to apply crypto to all kinds of new scenarios. Just looking at the papers on the IACR ePrint archive for 2017 gives you a good idea. Lately I've been making use of my knowledge of linear algebra, algebraic geometry, number theory, etc. I definitely used all of that at one time or another at the agency as well.
  3. Now that I'm more of a computer scientist, I'm going to say 2. :-)

CornyHoosier23 karma

Hello there! I work in IT Security myself. Quantum computing seems to be one of those topics that makes the professionals in my field grind their teeth because we're just not aware of all the implications or capabilities of this new technology.

Do you foresee any major structural changes (in regards to topology or hardware) to the current operation of "the Internet" when quantum computing becomes more standardized?

Also, one of our bigger concerns seems to be authentication. Will there need to be a bigger push into bio-metric authentication over AlphaNumeric-memorization or do you believe that some form of trusted authentication will come into play that can "thwart" quantum calculation?

My worry is that the world gets quantum computer before IT professionals can figure out a way to maintain password fidelity.

rabinabo29 karma

The current post-quantum crypto schemes would all involve some compromise, like larger keys, more involved computations, maintaining state (like in stateful hash-based signatures), etc. Symmetric crypto, like AES and hashes, would remain mostly the same as now, with maybe double the key size. Besides that, we should be able to secure comms in a similar manner to what we have now.

The process of adopting standards for post-quantum crypto is under way right now, as NIST is currently taking proposals, and hopefully, we'll have new standards within the next 3-5 years.

BassandBows18 karma

Hi! I am finishing up my third year in college with a double major in (Pure Mathematics) and (Applied Mathematics&Statistics). From what I've seen, working for the NSA is one of the few ways that a person can work with cool/real/pure-ish math and get decent money doing it. My question: How do I go about landing a (dream) job with the NSA? What steps should I take? What qualifications and experiences should I try to get first? Finally, do you like working there? Thanks for doing this AMA!

rabinabo26 karma

It sounds like you're already ahead of where I was at your age, because my background was almost entirely in pure math. It wasn't until I started at the agency that I really got into programming and more applied math. For experience, I would recommend taking computer science classes, like algorithms and programming. For more specific recommendations, I'd have to know more specifically what areas you'd like to work in.

I'd recommend looking into the student programs because you get to learn about all the things that the agency works on. I've known a lot of people that were in the co-op programs, and most of them came back to the agency in some capacity. Just keep feeding that curiosity, read the latest tech news, delve into some of the technical details, participate in coding competitions, etc.

I don't work at the agency any longer, but I enjoyed working there. It's a great place for me to gain some experience, and I've made lots of life-long friendships there.

BassandBows3 karma

I am looking for a non statistics based field. I have experience programming Java, Python, and Mathematica. Would this narrow anything down? Also how elite are these student programs? I know that I have the brain power, but I'm coming from a public university and I'm worried that I won't match up to the competition.

Thanks for the link though, it looks really helpful!

rabinabo8 karma

Yeah, I think you have a great start programming-wise, from my perspective. One thing I would suggest is to try out some of these online coding competitions, like topcoder.

My friends in the student programs came from all kinds of different schools, so I wouldn't hesitate to apply. The only way to know for sure is to apply!

nooblifts2 karma

To piggy back on this, I'm a community college student studying math. I was inspired to go back to school after reading Ted koppels Lights Out. What topics should an undergrad have a good grasp of to help set them up for work in security/cryptology?

rabinabo4 karma

From the math side, I'd recommend discrete math, algorithms, maybe linear algebra, intro to number theory and/or cryptography.

poorasian15 karma

What is your favorite complexity class and why is it F-Hard?

rabinabo16 karma

I kind of like plain old P.

Xalteox14 karma

How will the quantum revolution affect cryptocurrency/blockchain technologies?

MrSenorSan8 karma

Current popular blockchains like Bitcoin, Litecoin, Dogecoin and Ethereum will be made obsolete if they stay as they are.
New blockchains are taking QC into account, some of the current ones will most likely fork out to versions that will handle the QC challenge.

ItsAConspiracy10 karma

Ethereum is in fact forking to a QC-resistant version. The upcoming Metropolis release will allow users to choose their own signature algorithm, and there's already code for one of the post-quantum algorithms.

Proof of work is also vulnerable. QCs don't completely break hashes but Grover's algorithm could make them billions of times faster than classical miners. Ethereum is planning to transition to proof of stake over the next year or so.

rabinabo5 karma

That's awesome! I hadn't read about the Metropolis release. I'll have to look into what they're using.

throwaway-ama-fxn9 karma

Do you need a PhD to have a good career in math at the agency?

Does the agency support privatized dual use tech, made by former employees?

How do you like MD?

Does the agency support simultaneous work-study in math/comp sci?

Thank you for doing the AMA, and thank you for supporting our country.

rabinabo20 karma

Not sure what you mean by privatized dual use tech. There are some projects that got released to open source projects, like PIRK, for example.

Maryland is actually nicer than its reputation I think. There's lots of green space around, for one thing.

Yeah, there are definitely work-study programs at the agency. One that I used myself allowed me to work 20 hours and study for classes 20 hours. That's how I got my master's in CS.

CakeAccomplice129 karma

What are some currently practical examples showcasing the state of our control of quantum computing?

In other words, is there currently an existing functional quantum computer solving problems more efficiently than a classical one?

Doesn't have to be a ridiculously complex system, I'm just curious if the proof of concept exists in practice right now

iyzie30 karma

The D Wave device with ~2000 qubits can solve certain problems faster than a laptop. These problems can be solved faster using multi-core desktops or supercomputers, but I think it's impressive that a non-silicon based quantum technology can compete with modern intel processors.

Google says that they will soon have a ~50 qubit gate model quantum computer, with enough precision that it will be able to perform a well-defined (but also useless) task faster than any supercomputer in the world. Their theoretical scheme makes sense, and their experimentalists say it will happen within a year. We will have to wait and see.

rabinabo13 karma

Thanks, this is about what I would have replied with.

G3RTY6 karma

Can I hack the over ride, acid burn?

AncientRickles5 karma

I asked this last night and it got some interesting discussion. I would like your guys' take on it:

If Shor's algorithm turns factoring large composite numbers into a polynomial time problem, is it possible that a quantum computing algorithm could be found with sufficient to solve any NP problem (P=NP)? Are there any NP problems that we know for certain, say with mathematical proof, for which no polynomial time quantum computing algorithm can exist?

rabinabo2 karma

If you take a look at this paper by Bennett et al, it suggests that the best you can do with a general approach to NP problems is akin to applying Grover's algorithm to search for a solution, so you cannot do any better than a square root speedup without exploiting the structure of the problem. I found these notes by Scott Aaronson that explains it much better than I ever could.

I think the answer to the second question is also no, if you read my link above, specifically the "Quantum Computing and NP-complete Problems" section.

WhopperNoOnions5 karma

This may not be wholly related to your research, but how does your group see the use of neural networks growing in tandem with quantum computing, if at all? I have only a cursory understanding of both quantum computers and neural nets, but from my limited understanding it seems like quantum computers are particularly good at finding global minimums, which is what neural nets try to do in a lot of cases. Are there applications of one to the other?

Also thanks for doing this AMA!

rabinabo6 karma

Huh, I didn't know that existed at all, but there is some work on Quantum neural nets. I have seen a lot about quantum annealing though, where my understanding is that it may be able to use quantum tunneling to prevent from getting stuck in some local minimum.

mike_bolt5 karma

Am I mistaken that Shor's algorithm is the only known algorithm with quantum supremacy that poses a threat to encryption algorithms? If not, then why are you so concerned about the future of cryptography?

If it continues to be difficult to create a general-purpose quantum computer, then there may be less need to worry about quantum attacks that require hardware with lots of fault-tolerance. We may only need to worry about quantum attacks that will be feasible on the best imaginable quantum hardware. Do you have any insights about which cryptographic methods (or problem classes) may be broken first?

Do you think that Google will be able to break the quantum computing "record" with its new chip design? link

rabinabo3 karma

Yes, Shor's is the main threat to current encryption. One of the main reasons for my concern is that it is a really long process from creating a crypto scheme, to implementing it, to creating a standard, to actually getting used by a majority of users. Just that last step can take ten years or more, if I remember correctly from a great CRYPTO 2016 talk by Brian Sniffen from Akamai.

It seems like elliptic curve crypto is actually more vulnerable to quantum computing than RSA, because the small key size is actually a bit of a drawback.

I don't know if google will be the first, because they also have some competition from Intel.

Beanswithoutborders4 karma

I don't get this science talk but my question is are you guys the nerds from the simpsons?

rabinabo9 karma

Do you mean the scientist guy, or like Milhouse?

ConfusesNSAforNASA5 karma

Confirmed for Comicbook Guy type nerd.

rabinabo12 karma

Worst comment ever!

stillalone3 karma

I think there was a report a year ago (or was it two years) from the NSA that said something like elliptic curve cryptography was less secure than RSA because it was more vulnerable to quantum computing attacks or something like that. Can you comment on that? Is elliptic curve cryptography less secure?

rabinabo8 karma

The issue isn't really that ECC is less secure, but rather that the key sizes are so small compared to RSA for example. If you work out the numbers, one could attack ECC with a smaller number of qubits, so it will be vulnerable to earlier quantum computers than RSA. I had looked at this one relevant paper, but can't find it at the moment.

BTW, /u/stillalone, you're never alone on reddit.

jpb183 karma

Hey there!

What exactly will make most cryptography obsolete? Quantum computers that can easily decript the most advanced ciphers, find collisions on secure hashes, etc, or the communication channels that will be based on said technology?

xmeehan6 karma

Not OP, but the main threat to cryptography from quantum computing as I understand it is the ability to factor very large numbers. RSA, one of the most common public-key cryptography algorithms, is based on the idea that it's easy to multiply two large numbers together but much more difficult to take a number that's the product of two large numbers and return what those two large numbers are. Factoring allows you to determine the private RSA key from the public RSA key. (In general, it's done in reverse: you pick two large numbers and use them to compute your public and private keys, then discard the numbers.) A quantum computer has some special tricks that lets it compute the period of the function f(x)=ax mod N for an arbitrary a and where N is the large number you want to factor. The period of that function can then be used to compute the factors of N thanks to some group theory magic and Euler's totient function.

rabinabo3 karma

That's just the most direct application of Shor's algorithm, but it can also be applied more generally to any example of the hidden subgroup problem for what are called abelian groups. Examples include Diffie-Hellman and elliptic curve cryptography.

For things like hashes and symmetric key crypto, where there is no really discernible algebraic structure, the best that a quantum computer can do at this point is to apply Grover's alg to get a square root speedup. Practically, that means you can just increase hash sizes and key lengths by a small constant factor to compensate.

patb20152 karma

How would we know if the russians or chinese already have a working quantm computer?

rabinabo8 karma

Well, if I had a large enough quantum computer, I would try to reclaim some of those Bitcoin private keys that are probably lost forever, but you could see it in the block chain, long abandoned bitcoins suddenly being moved around.

TheNorthComesWithMe2 karma

How is this good for bitcoin?

rabinabo6 karma

It's not good for bitcoin, but they can have people migrate their keys to a post-quantum signature before quantum computers become a threat.

Flute_Cadenza2 karma

What departments/job titles are great for applied mathematicians wanting to work there?

rabinabo4 karma

At NSA? Lots of us had "applied research mathematician" as our title, but our actual job descriptions would vary pretty widely.

IAMA-Dragon-AMA2 karma

Unless I'm mistaken wouldn't an error correcting quantum computer capable of actually being a threat to our current encryption schemes require over a million q-bits. We don't scale up our current quantum computers in part because our q-bits have somewhat poor fidelity.

Unless there has been some remarkable way of scaling back the number of T-gates and the T-depth of a quantum computer like the one you'd need to crack any reasonable encryption scheme you'd see. Is there some recent paper I'm missing which cuts down on that number significantly or is this all just more speculative?

I don't want to dump on your field, quantum computing is an amazing science where a lot of progress is being made. I think the public tends to have an unrealistic expectation of the results these computers are capable of and I think part of that is the responsibility of researchers who announce the field as "making crypto obsolete". Especially since the field of Post-quantum cryptography is quite active.

rabinabo2 karma

In terms of the number of qubits these labs have made versus the number needed, we're still about as far away as we have ever been. The key difference is that we're on the cusp of a scalable design. Google is hoping to go from 6 to 49 qubits in the next year, which is a big deal imo. The key problem is whether one can apply current silicon fabrication technology to building a quantum computer. If that answer is yes, then you could see those numbers go up real quick. Research funding for quantum computer research is also growing rapidly, so it's difficult to gauge the rate of future progress. My main point here is really that we do not know, so to really guarantee security, you have to take post-quantum into account.

The main issue accelerating the need for quantum-resistant crypto is that we need it WELL BEFORE a large enough quantum computer is built. First of all, for communications that need long term security (like decades), you should definitely be concerned already, because organizations with large resources can store your comms now to break when they get a quantum computer. Second, the process to develop crypto algorithms, implement them, create standards, and get them adopted by the general public on their devices can take 10 years or more. I mean, we still have millions of computers running XP.

I'm really working in the post-quantum crypto area, but a major part of selling people on post-quantum involves convincing them that quantum computers are a viable threat.

KamehameBoom2 karma

Do you take offense to what Will Hunting said about the NSA?

rabinabo1 karma

I won't talk about what he said to the NSA, but at times he was unjustifiably mean to both Robin Williams and Minnie Driver. That I cannot abide, although he seems to have figured things out by the end.

BTW, I was actually a senior at MIT when they were filming Good Will Hunting, and I remember a few filming locations that were very familiar.

fiberwire922 karma

Is the NSA worried about quantum computers, or excited by their prospects?

rabinabo3 karma

Actually, the NSA has been especially vocal (for them) about the threat of quantum computers.

Borthralla2 karma

How many decades would you estimate until we have quantum computers capable of breaking modern day RSA?
What kind of applications would Quantum computing have outside of scientific research? Would it improve the performance of things like gaming and video editing?

rabinabo6 karma

I personally think that it's likely in the next 10-20 years. The difficulty about that making a prediction is that

  1. Not all the engineering is solved on how to scale up current tech.
  2. We don't know if/how fast the rate of research investment will grow.

One of the ways that you can tell that we have a ways to go is that there are several competing physical implementations of quantum computers still being actively researched.

Quantum computers aren't really general computing devices, so I don't think it'll be use for individual end-users for things like gaming and video editing. Currently, they can be used to solve fairly special problems. However, there will definitely be commercial uses. They can be used to simulate quantum interactions, which can be used to improve industrial chemical processes for example.

Stupid_and_confused1 karma

I'm a freshman studying computer science, with a minor in math. I am really interested in crypto, and would love to go to grad school for it. I have read up on quite a bit of modern/classical crypto, but know next to nothing about quantum computation and post-quantum crypto.

As I understand, RSA encryption wouldn't be viable due to Schor's algorithm being able to factor the public key in polynomial time. But, what about other currently used cryptographic schemes such as diffie-helman which relies on the DLP? Why would that be broken due to quantum computation?

To sum it up, I'm curious about what cryptographic schemes would be rendered obsolete by quantum computation, and what types of schemes currently have the most potential for post-quantum encryption.

rabinabo2 karma

Diffie-Hellman and even elliptic curve cryptography relies on the same fundamental problem, the hidden subgroup problem over abelian groups. Some of the post quantum primitives add noise terms that can only be removed by knowing some secret. In code-based crypto, it's knowing the exact code being used. In lattice based crypto, it's knowing the secret polynomial or matrix that you're multiplying by. With supersingular elliptic curve isogenies, it's knowing how one is navigating through this complex graph of isogenous elliptic curves.

netsecwarrior1 karma

What an interesting field to work in. It is reassuring that people are already trying to keep us secure against these theoretical machines.

Are you aware of any other major technical threats to cryptography? I've seen some discussion online about telepathy as a threat - how can you keep keys and passwords secure, when someone can read your mind?

rabinabo10 karma

I could sense that you going to ask me that. I think precognition is more of a threat, if they can guess your keys/passwords before you've even thought of them.

mittaltushant1 karma

I am a third year undergrad CS major planning to do a Ph.D in Cryptography, Computational NT/Algebra related field. So, my question is what motivated you to take up this job as opposed to entering academics and how different is it? Also, for people like me who have little chance of getting into NSA (am an Indian), what other options are out there ?

rabinabo3 karma

I had pretty much decided to go into academia all the way through grad school, but by the time I was almost done, I had changed my mind. Mainly, I wanted to be able to settle down in one place for a time. Continuing into several post-docs in the battle for a tenure-track position didn't really appeal to me, and I had practically no programming experience, so I really only applied to the NSA. The way I saw it at the time, I could either go to the NSA or work for wall street. At the agency, there is a great community of mathematicians, so that had great appeal for me.

Right now, there are many more options available. There are lots of really interesting work being done. I would try attending some of the conferences, like CRYPTO (there are many others around the world if you're not in the US of course). You can also try reading some of the current research to have an idea of the trends. I like to check the [IACR eprints](eprint.iacr.org/2017/) every week or so.

ConstantAndVariable1 karma

I'm currently studying for a BSc in Maths outside of the US and I've a few questions:

1) Concerning the backgrounds of the employees in this division at the NSA, you've mentioned that they hire people with BAs in Maths. What approximately would you say is the proportion of different qualifications? How common are MScs/PhDs in Maths/Computer Science/Applied Maths/Physics etc., and/or would most people primarily have Bachelors in Maths/Computer Science/Applied Maths etc.? In particular for new hires, what sort of qualifications are expected?

2) Currently, I'm taking a course in Cryptography which approaches it purely from a mathematical angle, and will be later doing a course in elliptic curve cryptography. These courses, in general, lack a programming aspect to them as they're pure maths modules. What I'd like to know is, coming from a pure maths background, would your work have consisted of more 'Pure Maths Research' style work or was it very significantly concentrated in actually implementing (by coding) cryptosystems/performing cryptanalysis on existing systems?

3) What made you decide to choose to work in industry rather than to try and secure an academic position after the completion of your PhD (to /u/rabinabo) and are there any specific areas of mathematical research aside from cryptography which you find particularly fascinating at the moment? What fields of mathematics do you find most exciting at the moment?

4) What percentage of your colleagues at the NSA would have been from outside of America? Were most employees American citizens before they were hired, or was there a very diverse range of backgrounds and nationalities recruited from across the globe?

5) As a mathematics student, particularly if one is considering going into industry rather than academia, one may often wonder "When am I going to use this outside of an academic context?" While often, the answer to this question is probably "Never", are there any areas of mathematics which you've used over the course of your career (either in the NSA, as a consultant, or in the small cryptography software/hardware company) which you were particularly surprised had a very useful and neat application? A related question, Cryptography seems like it covers a very broad range of areas (Number Theory, Abstract Algebra, Statistics, Combinatorics, Information Theory, etc.), which area in particular did you find was the most important and regularly used to your line of work? I believe you've mentioned below that your research focuses primarily on lattices at the moment, so this question should be taken in the context of your entire career rather than in your current position.

7) Final question, how are both of your days going? What do you like to do from fun outside of work? Where do you guys stand on the debate of whether a hotdog is a sandwich? And what toppings do you get on pizzas?

rabinabo4 karma

3) An academic career just didn't appeal to me any longer. I didn't want to join the struggle for a tenure track position, let alone tenure. Also, I found that I was a bit lost in the research, to be honest. For my thesis, I had to focus down on one small tree (in representation theory), and I felt that I'd never really get a grasp of the forest. I don't really keep up with the pure math research, besides just reading some of the posts on /r/math.

4) NSA only hires US citizens. They do have people from lots of backgrounds. Most of my family is from Cuba, originally, although I was born in the US.

5) If you're curious about whether something is used outside of academia, just try to google it, you'd be very surprised. I basically google everything. I remember being amazed that one friend in CS was studying category theory, and type theory seems to be a pretty active research area that I've been meaning to read more about.

As for what math area that I've found most useful overall, I think statistics is probably foremost, with linear algebra a close second maybe.

7) This is really fun. I've been a huge fan of reddit for a few years now, so this was a really fun change of pace from my usual work day.

I haven't been doing this much recently, but I love cycling. Actually, John and I have both ridden across the US, and we actually have another coworker that has also ridden cross country. I also just got a 3d printer recently, so that has been a huge distraction. I also just bought a Miata a few months ago, and I like tinkering with it.

If we're going strictly by the definition, I'd have to say that a hot dog is a sandwich, but I don't have to like it.

As for pizza toppings, I feel that I have to quote /u/OfficialValKilmer:

Pizza is one of the greatest creations on earth. I have tried almost every kind in the world. There is no bad pizza. Or toppings. Heaven is filled with melted cheese...

Rotom-Wash1 karma


How many hours of daily or weekly study are expected to become and to work as mathematicians of your caliber?


rabinabo2 karma

I'd be afraid to tally up all the hours, between undergrad, grad, grad2, and studying for work. I think the most important thing is to have a never ending supply of curiosity. When you see some new, interesting tech advance, look up the papers and keep following the citations until you get to something fundamental that you can understand, or until you find a gentler explanation. That'll give you an idea of the fundamental areas you'll need to learn about.

LoveandRockets1 karma

What other algorithms besides Shor's are there? That's all I hear about.

rabinabo4 karma

There's lots! Shor's gets all the attention because of the drastic implications for public key cryptography, but Grover's has mild effects on symmetric key crypto.

newbie6141 karma

What do you think are the pros and cons of the new Brave web browser from a privacy/security viewpoint?

rabinabo2 karma

I hadn't heard of Brave before, but it's really interesting! I'll have to read more about that.