Re:
Delving Bitcoin
Provable Cryptography for Bitcoin: An Introduction (Workbook)
I’m excited to share a comprehensive cryptography workbook that we developed for an interactive workshop on Bitcoin cryptography. This workbook c...
that was recently advertised
As I spent some time this summer working through this material (with a bunch of other people), I can heartily recommend it, but, it's not for the faint of heart! I think it would be much more useful to explain why the title is what it is - "*provable* cryptography". Without getting technical, let me give you some background that might inspire you to get involved:
The concept of "provable security" sounds a bit bland; of course you want to prove things are secure, rather than just hope it! But in the history of cryptography, it .. wasn't always like that. Pre- asymmetric encryption (think from Caesar cipher to Enigma machines, so until 1960ish), cryptography and cryptanalysis were in a constant battle - one side came up with clever ciphers, the other side found clever ways of breaking them. Like an arms race (except ciphers are not weapons! they're armor .. so, an armor race). As far as I know, nobody tried to *prove* the Enigma machine's complex cipher was secure at the time. But in the 70s and 80s, after Diffie and Hellman's groundbreaking work introduced practical cryptography without having to share a secret key (the DH protocols, and RSA around the same time), things started to change for a definite reason: these protocols were based on a deep "fact" (usually not a proven fact, but a belief) about number theory. The classic one is factoring: the "fact" that factoring a very large number takes an exponentially long time. Rapidly, many other similar "very hard problems" were found, the one most familiar to readers will be the "elliptic curve discrete log problem" (find the private key, given only the public key). Cryptosystems were being built with these "hard problems" as foundation.
And people started using the concept of "reduction", which is slippery logically but very powerful: I build cryptosystem A. If you can break A (notice: I'm not saying how, I'm just saying if you can break it *in any way*) with some magical machine, you can take that same magical machine and ... find a private key given only a public key. If you think about it, it makes sense to describe that as "reducing the security of A to the elliptic curve discrete log problem". The reason this gained traction through the 80s and 90s is because it circumvents the cryptographer-cryptanalyst war we mentioned at the start (at least, in theory it does!). The cryptographer doesn't have to consider all the different ways the cryptanalyst might break his system. He only has to believe that the math problem (e.g. factoring) is indeed hard, because if it is, and because he has a reduction, he knows that any such clever cryptanalyst is breaking the factoring problem, too.
I'll admit I balked a bit at this "backwards" logic when I first encountered it. I thought "hmm well maybe the clever cryptanalyst is going to use his technique against my cryptosystem A, and *actually* break ECDLP by doing it!". (I remember Greg Maxwell's response when I expressed this was "good luck" 🙂 ). But I hope you can see that this is generally missing the point, since the reduction isn't saying anything at all about ECDLP or factoring or whatever. It's just making a bridge from your specific thing, to the general "hardness" of the "big" problem like factoring. A bit like how money is useful because we don't need an unreasonable number of barter prices; everything is compared, numerically, with one central thing. Similarly there is a zoo of crypto protocols that use ECDLP as their "foundation", their security can be (even numerically) related to the security of that underlying thing.
As usual I'm now waffling a bit, but the main point I'm trying to get across is: "provable security" is based on these reductions, and in the "modern era" of cryptography, it's the main way you have any chance of navigating the huge complexity of answering the question "is this cryptosystem secure"? If you can reduce it to a known problem, you are done. Of course such reductions are sometimes wrong, and sometimes fail to model certain details that occur in real implementations, so they're not a panacea, but they are the best we have.
#cryptography
