Last Updated: July 09 2019

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, every time I add something new, so you are encouraged to revisit from time to time.

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 are(were) as real humans. Fortunately, thank to YouTube contributors, 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.

Prerequisites

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

• Prof. Paar's Introduction to Cryptography 2-semester course,

either as a whole, or partially on an as-needed basis. I'll assume familiarity with cryptography at that level.

These crypto bites cover topics that are taught in graduate courses on cryptography. If you're interested to teach yourself advanced cryptography, and you are really determined, you will find some general advice, an intermediary Coursera lecture, and an advanced MIT lecture in

• Advanced Cryptography

Though useful to know, nothing taught there is strictly required to understand crypto bites (unless I link to a specific lecture).

Covered Topics (so far)

• Riposte (1 intro plus 5 crypto bites) is a clever system for anomymous microblogging (as in tweets), especially designed to thwart mass surveillance based on the collection of meta data. 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. Unlike other mix-nets based anonymizers like Tor and I2P, Riposte is based upon a combination of three cryptographic primitives: secret sharing, writable PIR, and distributed point functions. We'll explore writable PIR on a conceptual level. Then we move on to describe distributed point functions which are a very useful tool to drastically reduce the bandwidth between clients and Riposte servers up to a factor of 1,000 or more. We then show a concrete (2,1)-DPF for the case of 2 servers, out of which 1 can be compromized without the anonymity being compromized. Topics not yet covered are the Audit server, which is required to prevent malicious users from thrashing the database. The Riposte paper describes such an Audit server for the 2 Riposte server scenario. Future work (as in: not in the paper) include designing an \((n, n-1)\)-DPF with \(n \gt 2\), which requires more than a PRF, i.e. zero-knowledge proofs of permutation. The Audit server protocol also needs to be extended to the \(n \gt 2\) Riposte server scenario.

• Key Exchange Protocols (1 intro plus 9 crypto bites) 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 series, we'll start with the obvious signing of the ephemeral keys, only to find out how a devastating replay attack which leverages ephemeral leakage permits long-term impersonation. Trying to fix the protocol by adding an element of freshness, we'll get to know the infamous identity misbinding attack, a.k.a. the Unknown Key Share attack, which has the reputation of being the destroyer of KE protocols. To mitigate UKS, we need to sign the peer's identity as well. But how do we prove that the resulting protocol is secure? This is where the Canetti-Krawczyk model enters the scene. Up until now, the KE protocols didn't hide/protect the parties privacy: anyone observing the traffic could tell that Alice was communicating with Bob, in an irrepudiable manner. To protect privacy, we look at the SKEME and STS protocols, and why they fail to do so. Drawing from these lessons, we'll explore the very important class of Sigma protocols, which provide either initiator- or responder privacy (but not both). All these 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.

• Secure Multiparty Computation (1 intro plus 10 crypto bites): 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. We then show how the Boolean AND function can be securely computed with a deck of cards, and how the SUM function can be securely evaluated using secret hiding/masking. Up to now, all parties were assumed to be honest-but-curious. In the face of malicious parties, more robust constructions are needed. We show Shamirs secret sharing scheme based upon polynomials which enables secrecy in the information-theoretic sense, and show how additions and multiplications are performed in the famous BGW protocol. If we're willing to make assumptions about the hardness of some intractable problems used in cryptography, we can construct other MPC schemes that preserve secrecy in the computational sense. These schemes use a very powerful cryptographic primitive: oblivious transfer (OT). Using OT, one can construct a 2 party scheme called Yao's garbled circuit. Another multiparty scheme uses OT as well, the GMW protocol. A protocol whose runtime complexity doesn't depend on the function implementing circuit's depth is the BMR protocol which runs in a constant number or rounds. Planned, but not yet covered topics include the TinyOT protocol, the SPDZ protocol, and the fascinating oblivious RAM (ORAM). The main lesson of this series are the feasability theorems. Finally, we should note that computations are fast, but the communications overhead between parties is high. This is the opposite with homomorphic encryption (covered in a dedicated series), where computations are slow, but communications overhead is minimal.

Topics Currently in Progress

• Theoretical Cryptography (5 crypto bites): 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. We start this series with a short essay which motivates this rigorous approach. We then turn to Shannon's concept of perfect secrecy which is information-theoretic but requires unpractically long keys (one time pad), and semantic security which is computational but allows shorter keys. It is computational in the sense that it allows an efficient adversary to break the scheme with negligible probability. Then we dive into the fundamental building blocks, a.k.a. cryptographic primitives and constructions like one-way functions, hardcore bits, pseudorandom generators (PRG), pseudorandom functions (PRF), trapdoor functions and so on. We'll see that in order to ensure IND-CPA, the most basic form of secrecy guarantee, we need probabilistic encryption. We'll also explore other basics like bit commitments and oblivious transfer. Advanced topics include new classes of hard problems which enable completely new cryptographic constructions that were not possible before: learning with errors (LWE) which is an instance of lattice-based cryptography, and cryptographic multilinear maps. We defer the discussion of zero-knowledge proofs and the underlying real world / ideal world simulation-based proof technique to a later series dedicated to ZK proofs.

• Homomorphic Encryption (work in progress): 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? Using learning with errors (LWE), an instance of lattice-based cryptography, it is possible to achieve this seemingly paradoxical feast. There is a catch though: due to the nature of LWE, errors grow a lot with each multiplication gate, until decryption becomes impossible. Therefore, some functions can be computed this way, others can't. We call this somewhat homomorphic encryption (SWHE). For a long time, it was believed that fully homomorphic encryption (FHE) wasn't possible, until Craig Gentry invented in 2009 a blueprint of bootstrapping. This construction has the drawback of imposing a huge computational overhead, which researchers have tried to overcome ever since using all kinds of tricks, leveled FHE and so on. An alternative way to view FHE is by introducing homomorphic trapdoor functions (HTDF). Since trapdoor functions are a basic building block, one can construct FHE schemes, including fully homomorphic encryption (FHE) and fully homomorphic signatures (FHS) with HTDFs quite naturally. We stress again that unlike with secure multiparty computations, FHE computations are slow, but the communications overhead between the client and the cloud is minimal. HE is an active research field. Trying to describe a moving target is a challenge. See also: HElib, Cryptographic Research Group at IBM TJ Watson Research Center.
• Verified Cypto (1 intro, 2 crypto bites, plus 6 stubs): We saw in the series Key-Exchange Protocols how difficult and tricky it is to get cryptographic protocols right. Before widely deploying new protocols like TLS 1.3, their key exchange and other subprotocols have 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, Tamarin) and semantic (CryptoVerif, EasyCrypt) levels. Those tools leverage logic programming methods that we know from PROLOG, and the π-calculus. But the best verified protocols need to be implemented in the (messy) real world. A never ending stream of attacks on buggy protocols and implementations has lead to a complete reimplementation of the TLS stack starting from specifications in F*, an ML-like language, verifying them with automated proofs and compiling them all the way down to low-level C, ensuring that the resulting code has been fully verified from the specification down to its implementation. Interestingly, HACL*, this verified cryptographic library is also extremely efficient and competes well with the NaCl-API-compatible NaCl and libsodium libraries. The low-level C library can be either compiled with mainstream compilers like GCC and Clang, or, if we insist on verification down to the assembly level, but foresaking aggressive compiler optimizations, one can also use a formally verified and verifying compiler, CertComp. All these tools have and are being used to design the upcoming TLS 1.3 protocol, and to provide a formally verified impletentation of it: miTLS. The goal of project Everest is to replace the whole HTTPS stack with those formally verified and verifiably implemented components.

• Crypto Currencies (1 intro plus 2 stubs): From a cryptographic point of view, privacy coins with opaque blockchains are particularly interesting. Case in point are currencies based upon ZK proofs like Zcash, and upon the CryptoNote protocol like Monero, which need to get some love and scrutiny by the cryptologist community, resulting in new designs like QuisQuis.

Planned Topics

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

• Zero-Knowledge Proofs: How can nuclear powers, which don't trust each others, verify the implementation of the disarmament treaty stipulating the size reduction of their stockpiles of nuclear warheads in such a way that the inspectors can be convinced that the agreed upon warheads and not some decoys are being shipped off to disassembly lines, yet at the same time without learning anything about the radiation signature of these warheads which reveal highly sensitive information about the internals of these weapons to the enemy? Questions like these can be answered[PGGE16] with a very important cryptographic construction: zero-knowledge proofs (ZK proofs). In such a proof, a prover can convince a verifier of the validity of a sentence without revealing anything to the verifier. ZK proofs are very important und used frequently in cryptographic constructions. We'll explore these in this series.

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

• 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 (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, especially if the paper is 2 or more years old.

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

• Authors homepages: even if a paper happens to be behind a paywall, you may still find it on (one of) the authors' home pages. Look for links like "publications" on those pages. Sometimes, only extended abstracts are available, which are still good enough, and other times, extended "full versions" of papers may be there, which were previously published and printed in an abridged version. In any case, authors' hosted papers are a great resource if you come up empty handed (even from SciHub). Unfortunately, they are no permanent resources: they can disappear without notice when the author moves to another institution, or when he/she passes away. Therefore, always save those files as soon as you can. The "publications" section of those homepages are also a great way to scout out and explore the field.

Talks, Presentations, and Lectures

• BIU Winter School on Cryptography: The Center for Research in Applied Cryptography and Cyber Security at Bar-Ilan University, Israel, has been organizing their highly regarded BIU Winter Schools on Cryptography since 2011, featuring talks by leading researchers. Topics covered so far:
  
  • 1. Secure Computation and Efficiency
  • 2. Lattice-based Cryptography and Applications
  • 3. Bilinear Pairings in Cryptography
  • 4. Symmetric Encryption in Theory and in Practice
  • 5. Advances in Practical Multiparty Computation
  • 6. Cryptography in the Cloud -- Verifiable Computation and Special Encryption
  • 7. Differential Privacy: From Theory to Practice
  • 8. Secure Key Exchange
  • 9. Zero Knowledge
• Cryptography Boot Camp: The Simons Institute and UC Berkeley organized in 2015 a Cryptography Boot Camp, featuring talks by leading cryptologists. The lectures are available as videos. Topics covered include:
  
  • The Mathematics of Lattices, by Vinod Vaikuntanathan
  • Fully Homomorphic Encryption, by Shai Halevi
  • Multilinear Maps and Attacks, by Sanjam Garg
  • Obfuscation, by Amit Sahai
  • Applications of Obfuscation, by Craig Gentry
  • Delegating Computation, by Yael Kalai
  • Secure Multiparty Computation, by Yuval Ishai
  • Garbled Circuits, by Benny Applebaum
  • Oblivious RAM (ORAM), by Elaine Shi and Daniel Wichs
  • Differential Privacy, Fundamentals to Forefront, by Cynthia Dwork
• Stanford University: (incomplete)
  
  • Dan Boneh: Cryptography I
• Technion
  • Hiroshi Fujiwara Cyber Security Research Center, Technion
  • TCE - Technion Computer Engineering Center
• Others
  • COST-IACR School on Randomness in Cryptography (2016)
  • IISC-IACR School on Cryptography (2018)
• (incomplete)

References

• [PGGE16] Sebastien Philippe, Robert J. Goldston, Alexander Glaser, Francesco d'Errico: A physical zero-knowledge object-comparison system for nuclear warhead verification. Nat. Commun. 7:12890. doi: 10.1038/ncomms12890 (2016). See also: slides, project overview with video.

Feedback

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