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