Hacker News new | past | comments | ask | show | jobs | submit login
A Graduate Course in Applied Cryptography (stanford.edu)
466 points by throw0101a on Jan 10, 2020 | hide | past | favorite | 76 comments

Related to this, in case anyone is wondering if Cryptography II course by Dan Boneh will ever be offered on Coursera (It's been listed forever but without a start date). He mentioned that it will but most likely after this book is finished.

I always wondered if there was a hidden way to get access to Cryptography II, using knowledge from the first course. Never could find any hint for that or anything.

That would have been fantastic!

I’ll believe it when I see it. I took the I course (which was excellent) 6 or 7 years ago and gave up on II after the third or fourth cancellation. Should also be goo if it ever actually happens.

Duke Nukem Forever finally came out 14 years later, so maybe we are half way there.

That seems like an ill omen because DNF was not only years late it was also not very good when it shipped.

I think people are hoping for Cryptography II to be more Terminator 2 than Duke Nukem Forever in terms of sequels.

Same here, Cryptography I was amazing but I've given up all hope of II. It's too bad, things had just started to get interesting.

Oh wow.

I loved Crypto 1, and was one of the small % that finished it and did all the extra credit on its first run in ... 2012 IIRC.

Been looking forward to part 2 ever since but I will admit having given up waiting!

It's been invaluable.

Let's not lose hope!

Chapter 16 focuses on post-quantum crypto, including lattices. I see that it (and chapter 17) remains unfinished. Boneh certainly knows lattice tools; it's interesting to me that he nor his students do not seem to be in a hurry to work on lattice-based crypto. Perhaps this is a signal that they aren't worried that a quantum computer capable of cracking current systems will arrive anytime soon.

Google's new quantum supremacy device has 1,113 single-qubit gates and 430 two-qubit gates.

Article "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" https://arxiv.org/abs/1905.09749 shows how to significantly reduce the cost of factoring integers and computing discrete logarithms. Implementation of the efficient device mentioned in the article requires 2.7 billion Toffoli gates for 2048 bit input. It could factor one key in 8 hours.

Microprocessors reached that high MOS transistor count less than 10 years ago. For example, 8-core Core i7 Haswell-E has 2.6 billion transistors (2014). If quantum computers follow Moore's law like conventional IC, it will take 40-years before they can factor 2048 bit RSA.

> Microprocessors reached that high MOS transistor count less than 10 years ago.

Note however that quantum computers can potentially benefit from existing lithography processes, so it may not take as long to scale up as we have already developed processes for very small highly integrated circuits.

We don't need quantum computers to be at microprocessor scale to make 2048-bit RSA factoring groundbreaking. If a quantum computer the size of a car can do it in 8 hours, it's sufficient.

It's extremely hard to maintain car sized superposition for 8 hours.

The devise itself can be huge, mostly because it's cooled, but the actual quantum state inside is just tiny chip.

I think, generally, the concern with quantum resistant cryptography is that, like homomorphic encryption schemes, it’s unworkably slow right now.

No, many schemes are acceptably fast. Eg isogenies, code based signatures, some lattice schemes, some hash based schemes. The key concern usually stems from the size of the primitive (signature size or public key size)

Have quantum computers managed to break any sort of cryptography at this point? Even schemes that have been broken by classical computers? I have heard so much speculation on this, for over a decade now, but I haven't seen anything close to application. Can anyone provide insight on this?

We haven't gotten quantum computers to do anything faster than classical computers, except possibly contrived problems designed to be fast on quantum computers.

We have factored some small numbers on quantum computers but nothing a classical one couldn't do in a split second. https://en.wikipedia.org/wiki/Integer_factorization_records / https://arxiv.org/abs/1805.10478

Quantum Computing is now at the stage that standard ICs have been at in the early sixties. Back than, chips where made of of a few dozen transistors and couldn’t really do anything. It will take a while for quantum computers to really become a threat to cryptography, though at some point they definitely will (in my opinion).

Regarding the „except possibly contrived problems designed to be fast on quantum computers“ part: That’s their entire purpose. They cannot and will never be faster for all applications compared to a classical computer. They are designed to solve some very special problems efficiently, such as solving dlog and RSA using Shor‘s algorithm or database search using Grover.

The key word you missed was contrived. The current problems solved to produce "Quantum supremacy" are basically "What would this quantum computer do?" and yup, the current quantum computers can answer that by doing it and a simulation is harder, but this is a contrived question.

Shor's or Grover's aren't contrived problems, they're real problems which is why they're interesting. And none of today's quantum computers can run these for non-trivial inputs.

What's Moore's law like for quantum computers?

We have Neven's law: https://www.quantamagazine.org/does-nevens-law-describe-quan... which states that quantum computers are getting doubly-exponentially better relative to classical computers. First, they are exponentially better than classical computers. Second, they are getting exponentially better. Hence, Neven's law. One needs to define "better" formally (with number of qubits, gate fidelities, coherence times,...) to graph progress, but the idea is that they can do more.

BQP is not NP. There is an exponential speedup for very few interesting problems.

arXiv:1805.10478 (and most non-Shor records on the wiki page) are hacks. They essentially reduce factoring to SAT, pick numbers so that the SAT instance is easy, and then solve that SAT instance. Which is a bad non-scalable way to factor numbers.

The scalable way to factor is using Shor, but Shor only becomes practical once we have thousands of qubits, and it breaks RSA2048 with about 20 million qubits. (For clarification, a "qubit" here is a noisy qubit.)

No, it’s not. Some implementations do even perform better than current public key crypto schemes.

Which post-quantum cryptosystems are more efficient than RSA?

I did not claim that they outperform RSA in particular and I would not call RSA a state of the art public key cryptosystem. Actually, I would strongly suggest against using RSA without first having a deep dive into the field of number theory. However, for extreme RSA key sizes (e.g. 4096 bit) NewHope does actually outperform RSA and definitely outperforms some ECC counterparts.

NewHope has not been proven to be quantum resistant. I think researchers generally believe that NewHope will be proven to be quantum resistant, but there is the problem of adapting Micciancio's regular lattice proof to ideal lattices.

That’s right, it hasn’t. Just as almost every other candidate in the NIST competition. However, none of the currently employed public key crypto systems has even been proven to be secure against standard computers and they can definitely be broken by a (powerful) quantum computer. So I would still favor taking a scheme that most likely is secure against quantum computing over one that can definitely be broken by it, especially if their performance does not differ too much anymore.

Nothing can be "proven" to be quantum resistant. Even if we can show a tight reduction to LWE, and we believe that LWE is efficiently solvable (let's say LWE is not in BQP), it is still possible that the cryptosystem at the given parameters is broken. In the classical case, it doesn't matter whether or not the RSA problem is "hard" (more formally, the RSA problem is not in BPP), it matters if the RSA4096 problem has an efficient solution for many real world instances. So, yeah, the talk of "proving" security---while interesting---isn't very useful.

>However, for extreme RSA key sizes (e.g. 4096 bit) NewHope does actually outperform RSA.

Yep, it's definitely a scaling thing. If it weren't then we could simply use Daniel Bernstein's (et al) proposal for Post Quantum RSA.


A useful primer for those un-initiated:

Cartoon Cryptography

1min animated series that explains cryptography with cooking analogies


> Most websites you use today have fake security. When you log onto their service, your password gets sent up to their proprietary servers. There they check to see if it is correct and grant you access to your data.

> Sure, their servers might be in a top secret location. But the problem is that they know your password. Which means any bad actor, like a rogue employee, a hacker, or a government agency can snoop on your data without you knowing.

What on earth?

So... my understanding---please correct me if I'm wrong---is that the current practice is to send the password in plaintext to the server over a TLS connection. While this might not be the coolest way to do this (there might be something like a ZK-proof) it is the standard way. Also, why is it not okay for the person who controls the server on the other end to have a plaintext copy of your password? We hash passwords to protect against a 3rd party who gets a data dump, not against people who control the servers. (If you control the servers, you can change the protocol!)

It's not OK for two reasons, one a tiny bit paranoid the other much less so

1. The server operator might accuse you of doing something offering as proof a record that "you" logged in, but actually they knew the password so it was them.

This seems kind of silly if the server is a forum about a video game you like and the consequence of the alleged wrong doing is a permanent ban. But if the server is your bank, and the consequence is they convince a jury you tried to commit fraud and you go to jail when actually their employee has stolen your money using access to your password... that's pretty serious.

2. People re-use passwords. They know they shouldn't, but they do anyway. So "of course" the operator of "Puppy Fan Forum" knows your password, but it's also the password for your Amazon account, and next thing you know there's $1000 of dog treats billed to your credit card going to the operator's home in Ohio.

Sorry for the late reply.

1. This is actually good news. It provides deniability. You can, for instance, do something bad and then claim that the owner did it.

2. People really shouldn't reuse passwords, but I see your point.

AFAIK there exist cryptographic protocols that can authenticate you without revealing the password to the server. They aren't standard though.

What I like is that your reaction is probably pretty common.

Imagine the reaction a person from the 18th century would have if I told them it's silly to burn things to make light. You're the 18th century person in this scenario. You have never seen an incandescent light bulb, let alone an LED so I'm clearly crazy right? Of course you burn things to make light, how else would it be possible?

There is no need to send your password to somebody in order for them to authenticate you as someone who knows the password. Symmetric PAKEs which do this are actually relatively common in new systems that had a cryptographer help design them today, Bob knows the correct password is "Sesame" and Alice tells Bob something which proves to Bob she knows it too, but even if Eve hears everything both of them say she doesn't learn "Sesame" and won't be able to satisfy Bob that she knows the password.

For real human passwords, verified by humans, like "What's my favourite vegetable?" there's a wonderful protocol the Socialist Millionaire's Protocol, which lets you play this out, each participant says what they think the password is, and the protocol tells them both if they gave the same answer. Because humans are in the loop this can use low quality passwords, if I try to "brute force" you by guessing every possible vegetable you'll get sick of me wasting your time and disconnect.

Better yet, asymmetric PAKEs make it possible for Alice to tell Bob a fact which Bob can use to verify that Alice knows some password P, but without Bob knowing P. Eve can hear everything they say and still doesn't know P and can't impersonate Alice.

This stuff is almost as old as the World Wide Web.

Huh? PAKE is fine. I didn't say anything against PAKE. Nothing you say here changes anything about the fact that the statements I quoted are nonsense. (Or misleading FUD at best, I get the sense they're trying to sell me some proprietary "solution" to this problem, but I haven't looked closely.)

Your "you're the 18th century person" comment is needlessly insulting as well, especially given that what you've commented is basically irrelevant.

> Nothing you say here changes anything about the fact that the statements I quoted are nonsense.

No, they're true, which is what makes your reaction so interesting. You might more successfully argue that this (other people knowing your password) is a trade worth making, but then as I explained you don't need to make this trade at all, so the value you're getting by accepting the current practice is zero.

The thing they're "selling" on that site (promoting) is a distributed system where only you can decrypt your own data. There are a bunch of situations where that's not applicable, but even in those situations the other party doesn't need to know your password - so why do most sites do this?

Mostly laziness.

> even in those situations the other party doesn't need to know your password - so why do most sites do this?

There are literally zero situations in which I would get actual real-world better security from a site not having my password, given (a) that they're properly hashing it, and (b) the password isn't used to encrypt any personal data.

Claiming that sites doing those two things have "fake security" is the kind of bullshit that smells like a marketing scam, which is exactly what makes me suspect they're selling something. (Again, without having any further evidence in that regard.)

Even if a site is using a password to encrypt personal data (basically the ProtonMail scenario), I still have to trust the site itself not to steal my password, so additional security provided in that scenario is marginal at best.

The claims are akin to "we use only 512 bit AES, sites with only 256 bit keys have FAKE SECURITY". It's at best extremely misleading, and hard to imagine that it's not some cynical FUD marketing technique.

> There are literally zero situations in which I would get actual real-world better security from a site not having my password, given (a) that they're properly hashing it, and (b) the password isn't used to encrypt any personal data.


Claims that this means Facebook weren't "really" properly hashing it or are otherwise an exception constitute a No True Scotsman argument.

It is _definitively_ less safe to do what is commonly done today. There is no _practical_ benefit and there are plenty of things that can go wrong.

Accusing me (op, not parent) of selling proprietary junk and not even checking makes you the FUDster.

Everything we do is Open Source.

Get your facts straight.

Yes, the NSA really did use backdoor access to servers to spy on millions of people.


So use better security, like real cryptography.

What are earth are you talking about? I'm talking about the vibe I get from a site claiming that sending a password over TLS is "fake security". That's a bullshit claim. Coming here into this thread to use a bunch of buzzwords ("Snowden" is not an argument) doesn't make your site look any better. I was quite clear in my comment that I don't know if you're selling anything, but someone who isn't selling anything wouldn't be incentivized to characterize the situation the way your site does.

> A useful primer for those un-initiated:

Great share. Pulsed thanks

lost me at the sixth word

If it's anything like the one they teach at Georgia Tech, this is a quite difficult course. Boneh's a great instructor though.

It just so happens that I just started the Georgia Tech course this week. What topics would you say are the most difficult? Any tips?

OMSCS or in residence? I noticed OMSCS just added an applied cryptography course - I’ll probably take it after I graduate.

Number theory.

This. I went into my 400 level cryptography class with 0 Number Theory knowledge as it wasn't a prerequisite. Big mistake, it should've been. My lowest grade in college and I still busted my ass.

That being said, it was incredibly interesting and I do not regret it.

Ditto, I ended up taking the course twice.

Who's teaching that course now? I recall Chris Peikert used to teach some tough crypto courses before he moved to UMich.


I had Boldyreva back in 2012-ish. She's an excellent instructor who knows the material well. The course material is quite challenging though. You'll have to be able to pick out attack methods or prove security on custom cryptosystems. Be prepared to put in many many hours of studying if this is an area which is unfamiliar to you.

I would love to see a diff between this version and the prior version (Version 4, Sep. 30, 2017) which I've consulted extensively.

I wish this book was in a public git, TBH.

Side Note - I really admire Stanford's commitment to open education. The professors there have released so much high quality material for free.


How much cryptography is actually used in commercial applications? Having hundreds of pages of arcane (but highly interesting!) theory is great, but if it's not applied to real systems, like in banking, then its usefulness is limited, to say the least.

Edit: I don't know why I'm being downvoted.

All of Part I and sections 10-15 of Part II are deployed ubiquitously in most of the world today. As is section 22 of Part III (WireGuard, WPA3, TLS, etc. use AKEs).

The rest of it appears to consist of "areas that theoretical cryptographers are refining in preparation for real world use". This is the stuff that will be deployed in the real world come 2030.

So, to answer your question: More than half of it is actually used today, and at least 80% of it will be used soon. If you're going to take a course in this, it's better to be ahead of the curve than behind it. (Otherwise, we'll all be suffering through textbook RSA ad nauseum.)

That's a lot more than I expected.

There's a conference going on right now at Columbia University in New York called Real World Cryptography if you're interested in seeing what the state-of-the-art looks like for real-world deployment.



You're being downvoted because the question looks like snark even if that isn't what you intended.

Other people have answered the direct superficial question: A lot of this stuff is used already to make stuff work. TLS (for HTTPS) has been mentioned, but if you have a work laptop it's probably using Full Disk Encryption, if you use git for revision control the content addressability that makes that possible is only safe with cryptographic hash functions, the reason a bored teenager can't listen in to all your mobile telephone calls is cryptography, the reason it's very hard (and ought to be impossible if they'd done a better job) to use a chip-and-PIN credit card without the PIN is cryptography and so on.

Now the more subtle question: Do you need any of this? Well no for a lot of jobs you don't, just as a car mechanic doesn't need a grasp of aerodynamics to do their job, but if they fancy designing jet aeroplanes that's going to be a problem. This course is about applying cryptography but it isn't an engineering bootstrap course, so it expects you to understand why rather than only learning how.

You're probably being downvoted because your post can be interpreted as incredulous without a basis in knowledge.

The answer, as others have said, is most of it. In my role in fintech/banking we are indeed using many of these things - digital signatures using traditional or elliptic curve keys, authenticated constructions built of block ciphers and macs, key derivation techniques using stream ciphers etc etc.

While we do not commit the cardinal sin (though shalt not design thy own cryptosystem), knowing how they work can be invaluable to working with them.

If the url starts with https:// it uses cryptography.


Cryptography is used everywhere, I assume that is why you are being downvoted.

Online banking would not exist without cryptography.

Perhaps on Internet yes, but you should also look up Minitel, the 1980s French interactive directory service that, among many other services, provided online banking from home. I think it mostly relied on physical (i.e. closed network) security as opposed to any cryptography.

In the 1990s, French banks apparently considered providing online banking on the open and public Internet as much riskier than on the closed and proven Minitel (and probably quite rightly so).

Interesting, thanks.

I Googled for minitel cryptography. The first result was your comment. I suppose that tells me there was no crypto on minitel, as well as that google doesn't miss a beat.

I think many of us would be happy for a paragraph on EdDSA!

Many years ago I took a class taught by Victor Shoup, which I found extremely difficult but overall a great experience. Really smart guy.

Time ago there was a free course promoted also by Nikko Hipponen on Cryptography and that was really well done.

What's the price via SCPD? Usual $5200?

A 4-credit course is $5000 and a 3-credit course is $3900 (don't ask me why the cost per credit for each are not the same). There is also a one-time $200 transcript service fee.

With that said, if your employer has an educational plan that can cover the cost, then it is definitely worth pursuing. I am working on a AI graduate certificate and have just completed CS 221. The level of rigor in instruction and course work is far better than any online MOOC course I've taken.

At 900 pages I can’t help but be humbled.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact