NSA Employees only

Overview

This is my collection of notes on Cryptography. Most of them cover research topics in a hopefully accessible way to newcomers.

I'll update this page often, each time I add something new, so you are encouraged to revisit from time to time.

Prerequisites

Readers should have prior knowledge in Basic Cryptography as presented in University undergraduate courses. Those of you who would like to catch up or to refresh your crypto-fu can take

either as a whole, or partially on an as-needed basis.

Crypto Lounge

Cryptology is more than a mere collection of papers, algorithms, proofs, software, etc. It is also a community of real people: researchers who dedicated their lives to discover and create this fascinating and very rewarding field. Once you've become accustomed to famous names like Rivest, Shamir and Adleman (of RSA fame), Diffie and Hellman (of DH fame), and many others, you may be wondering how these wonderful people look(ed) like in real life and how they were as real humans. Fortunately, thank to YouTube contibutors, we've got a nice collection of interviews, commemorative lectures, and bios in the Crypto Lounge.

Tools of the Trade

A working cryptologist needs to typeset papers, to verify constructions, libraries to program, and lots of handbooks too. Tools of the Trade features a list of useful links.

Covered Topics (so far)

  • Why Theoretical Cryptography: Cryptography matured from an art and engineering craft to a scientific discipline. Mathematical definitions to model the world, and rigorous proofs of security are bread and butter of all current research publications. This short essay explains that a naive composition of cryptographic primitives can still lead to security breaches even if the primitives are used according to specs, and emphasizes the need for security proofs from the design phase all the way down to the implementation.
  • Riposte is a clever system for anomymous microblogging (as in tweets), which unlike other mix-nets based anonymizers like Tor and I2P are based upon a combination of three cryptographic primitives: secret sharing, writable PIR, and distributed point functions. A Riposte cluster consists of a cluster of \(N\) servers, out of which \(N-1\) servers can collude, yet still are unable to tell which clients authored which messages. This series of crypto bites explores Riposte in depth.
  • Key Exchange Protocols are essential for Alice and Bob to set up a secure channel. Interestingly, KE protocols are incredibly hard to get right. Starting with unauthenticated Diffie-Hellman, we'll work our way up to various ways for Alice and Bob to mutually authenticate themselves, while also preserving their privacy against passive and active eavesdroppers. In this mini-series, we'll get to know the Unknown Key Share attack, the Canetti-Krawczyk model, the HMQV- and Sigma-Protocols. All those protocols are costly in terms of computation and communication overhead, so it may come as a surprise that lightweight protocols exist at all: implicitly authenticated Diffie-Hellman.

Topics Currently in Progress

  • Secure Multiparty Computation: In this scenario, \(N\) parties which don't trust each others, collectively compute a function, without knowing the inputs of their peers. We'll cover typical scenarios for this important cryptographic primitive as well as some theory, Shamirs secret sharing scheme based upon polynomials which makes it possible in the first place, and how additions and multiplications are performed in the BGW protocol. We'll also have a look at Yao's garbled circuit and the GMW protocol, which use a very powerful cryptographic primitive: oblivious transfer (OT). Here, computations are fast, but the communications overhead between parties is high.

Planned Topics

  • Fully Homomorphic Encryption: Can we compute on encrypted data, without decrypting it first? Suppose that we wish to compute on the cloud a function on encrypted data that we uploaded there, without giving the cloud the decryption key? It turns out that fully homomorphic encryption (FHE) is possible if we follow Craig Gentry's blueprint of bootstrapping. We'll explore FHE in this mini-series. Unlike with secure multiparty computations, FHE computations are slow, but the communications overhead between the client and the cloud is minimal.
  • Modelling the Real World with Attack Games: We'll revisit modelling of real world attacks with so called attack games, a mathematical tool to precisely define the assumptions we make regarding the capabilites and powers of legitimate parties and attackers.
  • Verification of KE protocols: as we saw before, key exchange protocols are tricky to get right. Before widely deploying new protocols like TLS 1.3, their key exchange subprotocol has better be thoroughly vetted and proven secure. Unfortunatly, such proofs are a tedious and error-prone manual task. Recently, automated tools emerged to help designers verify those protocols on syntactic (ProVerif) and semantic (CryptoVerif, Tamarin) levels. Those tools leverage logic programming methods that we know from PROLOG, and the π-calculus.
  • Verified Secure Libraries (\(F^{*}\)): Even if key exchange and other cryptographic protocols have been formally verified and are hopefully free of unintended weaknesses, implementing those protocols opens up a whole new can of bugs and implementation attacks like, e.g. downgrade attacks. A reason for this is improper reuse of state machines, i.e. carelessly shoehorning new protocols into the implementation of older ones as was done in OpenSSL, leading among others to the infamous Heartbleed vulnerability. In this mini-series, we'll explore ways how to automatically transform the specification of a hopefully verified protocol written in the \(F^{*}\) language into efficient C code, which even outperforms traditional manual C implementations, while at the same time preserving the specified protocol properties and security guarantees.
  • Zero-Knowledge Proofs
  • Crypto Currencies
  • (... and more)

Main Literature and Sources

My main inspiration for Cryptography in Small Bites are (advanced) textbooks, proceedings, papers, and talks / presentations given by researchers.

Textbooks

  • Dan Boneh and Victor Shoup: A Graduate Course in Applied Cryptography (draft 0.4): this is IMHO the ideal book for readers who have already taken an undergraduate course on cryptography and who wish to pursue their quest into advanced topics. You may be intimidated at first by the mathematical formalism, but fear not: it is mainly used to precisely express concepts than to torture you with convoluted proofs. I quickly grew to like this style. A main feature of this book is the technique of proofs based upon attack games. The exercises are exciting, since they show problems that are relavant to the practitioner. At the time of writing, the book hasn't been finished yet, but a fairly advanced draft is available as a PDF from Dan's website.
  • Jonathan Katz and Yehuda Lindell: Introduction to Modern Cryptography, 2nd Edition: To understand most current research publications, you need a solid grasp on the New Way(tm) to crypto, i.e. Modern Cryptography. Katz/Lindell is the reference textbook of this field, and pretty much required reading by all aspiring cryptologists. It covers a smaller breadth of topics than Boneh/Shoup, but does so in an even more formal way. I like both books a lot, but my personal preference remains Boneh/Shoup.
  • Oded Goldreich: Foundations of Cryptography, Volumes 1 and 2: Required reading for anyone who wishes to dive deeper into Theoretical Cryptography. Most more recent books, including Katz/Lindell are heavily influenced by Goldreich's FOC. I can't recommend it highly enough. Go get it, both volumes, and spend some serious time with it. Really. It's that good. Mathematical maturity is required, of course. Since it goes deeper than other books on Modern Cryptography, I'd recommend reading it after Katz/Lindell and Boneh/Shoup.
  • Yehuda Lindell (Ed.): Tutorials on the Foundations of Cryptography. Dedicated to Oded Goldreich. If you've enjoyed FOC and Katz/Lindell, you may still be hungry for more help w.r.t. theoretical cryptography. In this collection of advanced tutorials covering topics like simulation proof techniques, garbled circuits, homomorphic encryption etc., you have an opportunity to better understand and appreciate proofs in papers. I highly recommend this book. More and more chapters are being available online for free. (springer.com, book homepage)
  • Boaz Barak: An Intensive Introduction to Cryptography (pdf): this is a growing collection of lecture notes covering cryptographic materials taught at Harvard. It provides a whirlwind tour of contemporary cryptology. Recommended if you need to get a broad but shallow overview of the field, and if you seek concise explanations of modern paradigms like simulation, etc.
  • Victor Shoup: A Computational Introduction to Number Theory and Algebra, 2nd Edition (pdf). Number Theory is essential prerequisite to cryptography. There are many excellent books that cover this topic. My favorite is Elementare Zahlentheorie by Reinhold Remmert and Peter Ullrich, which AFAIK, hasn't been translated to English. Shoup's is also a great Number Theory book, and it is free too. Read it from cover to cover, or grab whatever you want on a need to know basis.
  • Menezes et al.: Handbook of Applied Cryptography of Applied Cryptography (pdf): somewhat outdated, but still an encyclopedic and concise presentation of cryptographic concepts, protocols, etc. by Alfred Menezes, Paul C. van Oorschot, and Scott A. Vanstone. This book is free too. I use it to look up concepts every now and then, and it certainly competes well against Wikipedia... and unlike Wikipedia, it IS a citable source.

Proceedings and Papers

  • LNCS (Springer Lecture Notes in Computer Science), Advances in Cryptology. These are proceedings of the CRYPTO, EUROCRYPT, and ASIACRYPT conferences: This is the main go to source for the cryptologists community. Covers the years 1988-2018. Freely accessible from link.springer.com via an academic VPN, unless you're ready to sell an arm and a leg, and a kidney too, to get them commercially (a few of the LNCS volumes, and many single chapters are freely available on open access basis for mere mortals though).
  • IACR Cryptology ePrint Archive: this is the best source for researchers in cryptology. It features a huge and freely accessible collection of papers by the International Association of Cryptologist Research, some of which have also been included in the LNCS proceedings. When looking for a paper, even if it is cited as LNCS, check IACR first, as you may get lucky.
  • ACM Digital Library: Every now and then, some papers covering cryptography may land in ACM publications. These are mostly older papers, before the community standardized on IACR/Springer. Here too, it is hit or miss whether you can get full PDFs as mere mortal, or if you need to sell a kidney for a subscription, or to VPN through your academic institution.
  • IEEE: Same as ACM DL, but even worse free availability of single articles.
  • Elsevier? Don't get me started on those guys. Any researcher publishing with them ought to be tar-ed and feathered and thrown into an oubliette, and anyone still promoting them belongs into the Bog of Eternal Stench. (sorry, but it had to be said).

Talks, Presentations, and Lectures

Feedback

Found mistakes in the notes? Suggestions? Criticism? Please let me know. Thanks.