We are ex-NSA crypto/mathematicians working to help keep the internet secure before quantum computers render most crypto obsolete!

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?

https://www.wired.com/2015/09/tricky-encryption-stump-quantum-computers/

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.

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.

(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?

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.

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?

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".

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.

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.

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?

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.

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.

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

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?

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.

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.

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!

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.

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.

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?

(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 2¹²⁸ 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 2¹²⁸ 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 2¹²⁸ 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.

That is the power of superposition! Yes, you can create quantum states with the outputs of all those 2¹²⁸ 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 2¹²⁸ 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.

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!

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. :-)

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.

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.

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!

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.

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!

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!

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?

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

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

I kind of like plain old P.

How will the quantum revolution affect cryptocurrency/blockchain technologies?

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.

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.

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

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

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.

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

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.

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.

Can I hack the over ride, acid burn?

Never send a boy to do a woman's job.

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?

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.

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

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.

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!

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.

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

Do you mean the scientist guy, or like Milhouse?

Confirmed for Comicbook Guy type nerd.

Worst comment ever!

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?

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)=a^x 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.

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.

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?

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.

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

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.

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?

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.

How is this good for bitcoin?

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.

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.

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.

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

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.

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

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

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

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

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?

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.

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

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

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

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.

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.

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.

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?

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...

Hello!

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

Thanks!

I'd be afraid to tally up all the hours, between undergrad, grad, grad^2, 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.

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 ?

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.