A #QuantumNative Engineer's Bookshelf

Quantum computing involves three major technical areas: mathematics, physics and computer science and engineering, and a fourth, important area: society. What does a new engineer, or student, aspiring to be a #QuantumNative need to know? Unlike some other researchers, I do not think it's necessary to learn physics first, or computer science first. I think you can dive straight in and learn quantum computing without insisting on quantum mechanics as a formal prerequisite. In fact, that's how you become #QuantumNative -- by learning quantum computing in parallel with classical. But, I do think there is  a structure to all of what you need to know, and an ordered walk through that will ease your way.

One of the duties of a university is to create a curriculum that provides structure to the body of knowledge. A book provides structure to a subset of that knowledge. Research papers move us forward, but assume a lot and ignore even more. Simply hopping around the web, looking for what you need at the moment, leaves gaps and causes you to miss things that an engineer with a more carefully curated set of knowledge will pick up on. Build your mental toolkit well, and you will be rewarded.

While books aren't the only way to learn, they are perhaps my favorite, so let me do this in terms of a bookshelf. These are not merely trophy books to look good, they should be used; by the time you're my age, they should be battered, coffee-stained and full of highlights and notes in the margins.

Many of these titles can be swapped out for similar, in some cases more modern, ones, but a few are truly unique, and several have their own Wikipedia pages. I think you'll see which are which.

Of course, if you're an undergrad, getting through all of these in four years will require focus and dedication, while at the same time, you must also keep up your social life, physical and mental health, and non-technical learning.  But hopefully these books will help guide you in good directions as your career develops.

Popular Science and on up to Beginners' Recommendations

• Hillis, The Pattern on the Stone: my single favorite popular science book on what a computer is.
• Conery, The Imposter's Handbook: hard to do better than this for a quick-and-dirty tour of CS, if you program a bit and are trying to get oriented to the more formal aspects, as well as the "secret handshake" lingo that gets tossed around by experienced hands.
• Fortnow, The Golden Ticket: the best layman's introduction to computational complexity.
• Williams and Clearwater, Ultimate Zero and One: when I was getting started in quantum computing, this popular science-level book cleared up a number of concepts for me. Now there are many popsci books on quantum, so it may have been surpassed, and certainly some will be far more up to date, so I don't mind if you swap this one out for a favorite of your own -- but it worked for me, and it will work for you.
• Feynman Lectures on Computation: now quite old, and always quite idiosyncratic, but I was there; you'll find my name in the acknowledgments at the beginning. Feynman opened my eyes to the ideas of computation, perhaps even more than Carver Mead, from whom I took CS1 three years earlier. The book is deceptively simple; you can understand most of the content with minimal background, but that doesn't mean it's really a beginner's book. This will, inevitably, force you to rethink what you know about computers. What a broad-ranging way of thinking...
• Sutor, Dancing with Qubits: this is intended to be, and is quite successful at being, more than a popsci book, but I've put it here because of its accessibility and how little it presumes you know; it begins with the very basics of binary numbers and complex numbers. The book is almost evenly split between background material (the first 200 pages) and quantum computing (the next 250). Yes, there's quite a bit of math in it, so it's more intense than a popsci book, but you won't regret it. Perfect for college freshmen. Aspiring #QuantumNative engineers could do far worse than making this the first real CS book they buy.

Mathematics (Both Pure and Engineering)

I have opinions on the topics, but fewer on the choice of books. Feel free to improvise here.

• Margalit, Rabinoff, Interactive Linear Algebra: as it happens, this will not only teach you piles and piles of important math, it will also show you what a textbook can be in the modern era.
• ...some calculus book or another: differentiation, integration, ordinary differential equations, introductory partial differential equations. I learned all this, and linear algebra, from Tommy volumes 1 and 2, which have a unique pedagogical approach. I recommend Tommy, but with no real experience with other books I can't much compare.
• ...some probability book or another: both discrete and continuous.
• ...some statistics.
• Jungnickel, Graphs, Networks and Algorithms: Why isn't graph theory core to more engineering programs?!? It's usually relegated to graduate school. As computer engineers, we learn about spanning trees, shortest path and directed acyclic graphs (as in compiler optimization), but there is so much more...Diestel is the classic but is heavy going, definitely a graduate-level text. This book is a good compromise, but feel free to substitute Diestel or something else.
• Oppenheim, Willsky, Hamid, Signals and Systems: you gotta know Fourier transforms and other transforms. Gotta. As in, must, required, not optional.  Fourier is fundamental, but quadrature modulation (used in the not-quite-extinct NTSC) was maybe the most interesting thing I learned, simply because I found it so counterintuitive that it worked at all. I learned from the first edition of this book. This book appears to be considered a classic, but again feel free to substitute.
• Kleinrock, Queueing Systems: Volume 1, Theory: this will change the way you think about computer systems, networks, and even going to the bank. Depending on the university, often taught to graduate students in electrical engineering.
• Cover and Thomas, Elements of Information Theory: information theory is its own distinct field -- not just math, not electrical engineering, certainly not pure computer science -- but I have reluctantly categorized it here. This is the classic text for classical information theory, though the basics are actually covered quite well in Wilde's quantum book, so perhaps you don't need both.

Computer Science

I'm including algorithms and machine learning here. Notice that there isn't really a pure theory book here focusing on complexity theory, but we have Fortnow above and Aaronson below.

• Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms: this book will repay every moment you put into it.  It's more than just algorithms, it includes a lot on data structures and of course assesses the complexity of algorithms and structures, as well.
• Guenin, Könemann, Tunçel, A Gentle Introduction to Optimization: a very mathematically-oriented introduction, I have used this book in my class.  I think it's a good intro to linear programming and the seminal simplex algorithm, for matrix-oriented optimization. I didn't find the math-oriented approach to be as enlightening for graph problems; I didn't even recognize Dijkstra's shortest path first algorithm for what it was in the unfamiliar notation. Overall, I think the book lives up to its name. If you want to substitute Papadimitriou and Steiglitz's Combinatorial Optimization: Algorithms and Complexity here though, I think you have made an excellent choice.
• Russell and Norvig, Artificial Intelligence: A Modern Approach: a must-have for a complete bookshelf, this covers everything up to the machine learning revolution below, focusing on GOFAI and symbolic and algorithmic techniques. I learned the A* algorithm from this, for example.
• Goodfellow, Bengio, Courville, Deep Learning: a just-right book, in the right place at the right time with the right depth, written just long enough after the revolution of 2012 to digest its importance, and soon enough to be timely. With the above, a great pair.
• Petzold, The Annotated Turing: I have several books on Turing, and several other books on the history of computation, but I am by no means an expert on the topic. Out of my modest collection, though, I would tap this one. There is so much more in it than just Turing's seminal paper, but it stops to explore every nuance. It really changed the way I view Turing machines.
• Knuth, TAOCP: do not buy these books until you have decided to dedicate your life to computation. But once you have made that decision, and once you think you understand algorithms, buy these unhesitatingly and spend as many hours with them as you can. In the problems sections alone you can find topics for an army of Ph.D.s. These books, perhaps more than any others on the list, will cause your hair to stand on end when you finally grasp a topic.
• Numerical Recipes: I believe, if you're going to create quantum computers that surpass classical ones, you need to have something of an organized understanding of how classical computers do numerical computation. Of course you'll find some of this in Knuth v. 2, and in any good book on algorithms, but the focus there is generally on higher-level data structures and algorithmic approaches, rather than the details of the computation itself. It used to be that software engineers had to write a lot of math code themselves, but these days good libraries for linear algebra, statistics, transforms, and numerical methods for differential equations are available. This is good for programmer productivity, software portability, and even performance, given that not everyone wants to speed months tuning code.  But it's bad for learning about the underlying machine and methods, which I think are important for engineers to know. These days, also, a lot of purely numeric code can run well on GPUs, which is a whole other matter involving a lot of learning about data parallelism. So, the book Numerical Recipes is likely outdated, but I haven't yet found a substitute.
  Asking about this caused quite a conversation on Twitter, where the general recommendations were "function libraries" and "ask on Stack Exchange", both of which are great but don't build organized understanding. People also hastened to point out that the software libraries themselves that accompany the book are licensed commercial software, and the free libraries and language features have made them less valuable. Moreover, some people don't trust the material, and recommend Netlib or any of half a dozen other implementations instead, but what I'm after here is an understanding of how to implement numerics.  I'd say this is optional.
• Foley, van Dam, Feiner, Hughes, Computer Graphics: all right, this is really optional, but you'll learn a lot about how math and computing go together in the real world, and how data reaches humans as information is an important topic.

Computer Engineering

What's missing here is a good book on the modern state of VLSI, including its limitations. There is some material on semiconductor physics in Gershenfeld, below, though. I have, reluctantly, left databases and web/information systems off this list; we have to draw the line somewhere. A complete understanding will extend to parallel programming and to distributed systems, as well.

• Hennessy & Patterson, Computer Architecture: A Quantitative Approach: I have had multiple copies of the classic as it has evolved over the last thirty years (one signed!). This is nominally a graduate-level text, and it's very tempting to put in the more basic Hardware-Software Interface as a nice introduction to how computers actually perform their calculations, but the important ideas are presented so much more powerfully here.
• Arpaci-Dusseau and Arpaci-Dusseau, Operating Systems: Three Easy Pieces: a very nice overview of key principles in an operating system, organized around virtualization (of CPU, memory, devices, even whole machines), concurrency, and persistence. I used to use Tanenbaum's Modern Operating Systems, but I'm afraid it's now too old, out of step with current practice. Sometimes the structure and humor in OSTEP both feel a little forced, and I would do things a little bit differently if I were writing, but overall I think this is the best introductory book on operating systems out there.
• McKusick, Neville-Neil, and Watson, The Design and Implementation of the FreeBSD Operating System: building on decades of its predecessors (I'm especially fond of the shorter and admirably lucid, but now outdated, book on 4.3BSD), this is the single best explanation of the structure of a OS known to humankind. Read this book!
• Aho, Sethi, Lam and Ullman's Dragon Book (well okay, that's not the formal name): Most people would place a compilers book under CS, even under theory, but I view programming languages and compilers as one of the three pillars of computer systems, alongside OS and architecture -- a legacy, I suppose, of having first been introduced to leading-edge computer systems research by reading an ASPLOS proceedings. You simply must learn about lexical analyzers and parsers and their relationship to finite automata and pushdown automata, as well as code generation and optimization. Yes, yes, there's a strong connection to theory here -- that's the point.
• Kurose, Ross, Computer Networking: a Top-Down Approach: obviously -- obviously -- you need a book on networking, ideally one that focuses on the Internet and its protocol suite, but that understands telephone networks, both fixed and mobile. Kurose seems to be the introductory textbook of choice these days, but I'm okay if you have a different choice.
• Stevens (and Fall, on the recent edition), The Illustrated TCP/IP (vol. 1 and 2): you also need to understand the joys and pains of creating implementations of the Internet protocols. This might feel secondary if you're working in quantum computing, rather than networking, but it's ultimately part of understanding computer systems. This book influenced many people. After Stevens died, I was at a conference where his wife picked up a lifetime achievement award in his honor, and there was a standing ovation and people were crying.
• Jain, The Art of Computer Systems Performance Analysis: another broad-ranging must-have.

Software Engineering

Michał Stęchły pointed out that I didn't have SE on this list. What an oversight! More coming soon.

Physics

Physicists, both experimental and theoretical, will be shocked at how few books I list here. Of course, the more physics you know, the better your understanding of the devices will be, but in fact to become a quantum software engineer, surprisingly little true physics is required. In today's NISQ environment, I'll venture, a higher requirement for physics is required than will be the case in a decade or so -- just as many great software engineers have a basic grasp of computer architecture but almost no grasp of the underlying semiconductor physics in computer chips.

Quantum physicists will recoil in horror at diving straight into quantum computing without learning about momentum and forces and energy, but I think you can actually defer much of that learning until later. I do think learning about damped harmonic oscillators is valuable, and that does require some of those other topics, though. Also, make a pit stop for Boltzmann and a little bit of thermodynamics and statistical mechanics when you start getting into decoherence, but don't get bogged down there -- those topics alone can be a career. Electricity and magnetism nearly killed my interest in physics; I really struggled with Maxwell's equations in large part because I didn't understand partial differential equations yet. So, if you find yourself losing momentum(!) here, shift to a different approach and come back for the physics later. You'll be surprised how much of it seems easy, or even obvious, after a little perspective.

• Feynman Lectures on Physics: available in a nice, online form, at least in English. (The paper edition has been translated into numerous languages, including Japanese and Russian.) Somewhat dated -- who does physics in feet, even in the 1960s? -- and perhaps the closest to "trophy" books of anything on this list, but the explanations of concepts are still as crystal clear as the day Feynman gave them.  Most of the topics above can be studied straight out of this set.
• Crawford, Waves: Volume 3 in the Berkeley series, this is the one I learned from. Waves in 1, 2, 3 dimensions, standing waves, diffraction, propagation, all this just sits in the back of your brain once you've learned it and influences how you understand other ideas -- especially optics and quantum mechanics.
• Hecht, Optics: I learned from an earlier edition of this, and use the current edition in my own group. For our stated purpose of making #QuantumNatives, perhaps the single most important physics topic and book; understanding interference patterns and waves in general is critical. I think you can do this without the Waves book above, but put them together and you have a powerful understanding.
• French, Taylor, An Introduction to Quantum Mechanics: eventually, yes, you'll want to learn this: how spectra work, energy levels, atomic structure, bonding, wells and tunneling, etc. There are lots and lots of books on the topic. I learned from this one, but you can easily substitute here.
• Saleh, Teich, Fundamentals of Photonics: I hesitate to even put this on the list; I have a copy but refer to it only very rarely, compared to the other books here. Most of what beginning engineers need to know is covered more than adequately in Hecht, but coupled with Hecht for fundamentals and the more abstract Gerry & Knight, the three books feel like a good set. I'd call this a low-priority acquisition and read, unless you're doing experimental work.
• Gerry, Knight, Introductory Quantum Optics: I'm probably betraying my current preoccupation with quantum networks here, but I think this is a good topic that will aid in an understanding of quantum hardware more broadly, and this topic is surprisingly not covered in any depth at all in Mike & Ike. Perhaps optional, but I've found this valuable. In fact, though, I acquired it fairly early in my quantum career, and I initially found it rather opaque. As my skills have grown, though, I have referred to it more and more often.
• Gershenfeld, The Physics of Information Technology: one of my favorite books. Not flawless, but where else will you learn about optical fiber, magnetic disk read/write heads, and semiconductor physics in one place? (Man, I'm citing a lot of books from MIT in this list!)

Cryptography and Security

Note that the security book probably belongs up under Computer Engineering rather than here, but I put it here anyway. If cryptography weren't such a juicy, well-funded topic for quantum computing, I might not have a separate section here, but in the context of growing #QuantumNatives, it's essential.

• Bishop's Computer Security: Art and Science: security is a topic that far too many of us learn in an ad hoc fashion. This 1,400-page tome should help you realize that it's an important and rigorous field, and not something to be trifled with. Most universities will have at least one course on the topic, take it! Oh, and this book dedicates only about 10% of its length to cryptography itself, another indication of how broad and rich the concept of security is.
• Schneier, Applied Cryptography: is there a better book than this out there?  It's now quite, um, mature, but it's so lucid, it's a classic. It also goes into more cryptographic corners than Bishop, including things like zero-knowledge proofs, and so might be a better fit for quantum folks than Bishop...if only there were a 3rd edition. The second edition is new enough to have a few paragraphs speculating about quantum computing, but old enough to just predate AES.
• Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography: this one is definitely optional, I hesitated to even include it here. But if you want to go further into the field, there's a lot here that's hard to find anywhere else in such a comprehensive, organized fashion. Again, though, 20 years old.
• Singh, The Code Book: a readable history of secrets, and more up to date than Kahn.
• Kahn, The Codebreakers: 1,200 pages of goodness, if a bit of homophobia thrown in, which certainly occurred in the statecraft of spying through the years. Originally published in 1967, before public-key cryptography and the disclosure of Ultra; updated but not very effectively some years later. (See my review.)

Ethics and Society

I believe this is critical to the development of responsible, mature engineers, but I don't have a single, comprehensive, neutral point of view book for the reading list. Recommendations?

• Peter Neumann's Computer-Related Risks. To the best of my knowledge, there's still nothing else like it. Peter is still the chair of the ACM RISKS Forum. If you don't have a healthy respect for what can go wrong with, and as a result of, computing technology, then you are Icarus incarnate. (The book is 1995, and availability is apparently limited; is there a more modern equivalent?)
• Your Computer is on Fire: I found this book uneven, and I don't think it provides a well-rounded, comprehensive survey, but it's still probably the best book-length thing I've read on how technology influences and is influenced by human biases and problems. If you want to replace or augment this with something more on the ethics of computing technology, including race and AI, the surveillance society, etc., I am okay with that. Reading the news every day and thinking about its implications is necessary but not sufficient, IMO.
• Failure to Disrupt: Perhaps the best cautionary tale I have read on computers and society, showing that technology alone is not enough. This might feel off topic, but I think everyone should be aware of the limitations of our ability as engineers alone to remake the world.
• Something on the history of technology and how it has been used both for good and for bad, and how it is reshaping society.

Quantum Computing and Information

Finally, we come to the core topic itself, if you're aiming to be a #QuantumNative engineer. We've already seen Dancing with Qubits and Ultimate Zero and One above, so here we go deeper. There's actually quite a bit of overlap among these, but you'll find the varying perspectives useful. It would be nice to have a good one on hardware, and an up-to-date one on algorithms. Both topics are moving too fast, though. Update: we now have a great book on quantum hardware, see the last item in the list here.

• rdv & satoh, Understanding Quantum Computers: not a book...yet. Broad-ranging and very introductory, this covers about twice the material of a popsci book, covering key ideas as well as some aspects of the business and some chats with important researchers. After working through this course, you'll be ready to tackle Mike & Ike.
• Rieffel and Polak, Quantum Computing: A Gentle Introduction: until the advent of Dancing, this was the book I recommended for a first serious book on QC. It's still good. More on algorithms, less on background math and nothing on implementations and decoherence.
• Nielsen & Chuang (or, Mike & Ike), Quantum Computation and Quantum Information: this is the book you must have on your bookshelf. Yes, it's now 20 years old, but it still hasn't been surpassed in comprehensiveness. (Perhaps it's impossible to have one single book on the topic now, like having one book titled "Computer Science".)
• Kitaev, Shen and Vyalyi, Classical and Quantum Computation: A short and rigorous but remarkably clear book, I found this an excellent complement to Mike & Ike. It cleared up a lot of things I found opaque in Mike & Ike.
• Preskill's Lecture Notes for Ph/CS 219: Preskill has a solid claim on being the best explainer in the quantum business. His chapters date back as far as 1996, and as recently as 2018. The explanation of entanglement is straightforward, provided you understand the notation. These chapters are free, as well as incredible content, and so are a great place to start before you begin stocking your shelves with expensive books.
• Wilde, Quantum Information Theory: covers the theory of information -- given a certain amount of noise, how much information can a channel carry? The book covers classical channels (Shannon theory) well, before moving into quantum.
• Asfaw et al., The Qiskit Book: A rapidly-evolving introduction to quantum computing using IBM's quantum computers and the Qiskit Python toolkit. Couple this with the other books here, and your gut-level feel for how quantum computers work, and how to design algorithms for them, will grow rapidly.
• Aaronson, Quantum Computing Since Democritus: about a third of this is non-quantum computational complexity, so it will serve as our pure theory book. Very few equations, and some of Scott's quirky humor, but make no mistake, this is a serious, rigorous book.
• rdv, Quantum Networking: hey, you got a better suggestion? In fact, the ten or so hours of video that makes up the bulk of our own course, "Overview of Quantum Communications", is now available on YouTube. With apologies, some of the materials such as quizzes and slide PDFs are still under lock and key, but we hope to make public a free text based on the course soon.
• Lidar & Brun, eds., Quantum Error Correction: this being a collection of chapters from different authors, (the only such book on this list), and now also mature, it would be nice to have a more cohesive and up-to-date book, but I don't know of one. Lidar & Brun's introduction on decoherence in quantum systems is probably the best summary of the topic I know of, which is what tips the balance here instead of just recommending a research paper, regardless of how good it is.
• Majidy, Wilson, Laflamme, Building Quantum Computers: Oh, this is a fantastic book!  This is exactly what we need. Everyone working in quantum computing systems should get a copy of this.

The Freshman Short List

Okay, okay, all that's way too much. Where should I start? With a sigh and a heavy heart (I hate shortening lists), here is one book each to start with from the largest of the above categories (plus one more).

Note that I only included one math book. You can get surprisingly far into quantum computing with nothing more than complex numbers, summations, matrix multiplication, tensor products, and the rudiments of probability. Sutor has not a single integral in the book. But to move more deeply into quantum mechanics, as well as into Gershenfeld and into the nonlinear optimization of deep learning, you will need not only differentiation and integration, but also the basics of partial differential equations. You shouldn't let math intimidate you out of working in this field, but at the same time, you should never stop trying to learn more math.

Of this list, Hennessy & Patterson, Gershenfeld, and Mike & Ike are probably most commonly used as graduate-level texts. Certainly, you should be prepared before tackling each of them, but ambition will be rewarded with an accelerated arrival at the ability to discuss these topics at the highest plane, with professional engineers and researchers.

So, the Freshman Short List:

• Sutor (488 pages)
• Margalit & Rabinoff (??? pages)
• Cormen & co. (1,320 pages)
• Hennessy & Patterson (936 pages)
• Hecht (720 pages)
• Gershenfeld (388 pages)
• Bishop (1,440 pages)
• Mike & Ike (702 pages)

That's 5,994 pages of paper, plus the equivalent of several hundred more in interactive web pages. If you're already a budding programmer, a dedicated 10 pages/day will get you through those by the time you're a junior (10 pages might be 20 minutes or several hours, depending on the content, how much background work you have to do to understand the topic, and whether you diligently do enough of the homework problems). That would make an excellent goal.  If you're not much of a programmer yet, you'll move slowly through Cormen; learning how to extend from a few lines of code to understanding the abstractions in algorithms takes time and patience. (I think that's one of the biggest intellectual hurdles I have ever had to guide students through, and needs much more attention in CS/CE/SE education, but that's another post entirely.) There's no harm in taking your time, keep up slow and steady progress. And don't hesitate to ask questions.

Good luck -- and come join my group!

Revision History

• 2020/5/26: First published.
• 2020/5/27: Placeholder for SE added.
• 2021/6/15: Added some words on ethics and society, but only a reference to Neumann's RISKS.
• 2022/1/12: Added Failure to Disrupt and Your Computer is on Fire, and a link to our Intro to Quantum Communications videos.
• 2025/8/1 Add Majidy, Wilson, Laflamme.

3.3 Digging into the Cryptanalysis of IPsec

(See the previous installment or the top level of this series of posts.)

What is the recommended lifetime of an IPsec Security Association today?  This is the question that has proven to be so hard to answer, and that has led me wandering all across the web.  Probably the most relevant source is, naturally, the mailing list where most of the design work is documented.

One early, relevant message from 08 March 1995 carries the quote:

"I think 2^32 is a better bound than 2^43, at least for certain modes
of DES. For instance, after 2^32 blocks in CBC mode, you expect to see
two identical ciphertext blocks, say c[i] and c[j]; the difference
between their predecessors will match the difference between the
corresponding plaintext blocks, i.e.,
p[i] xor p[j] = c[i-1] xor c[j-1]
Information thus starts to leak after 2^32 blocks (square root of the
message space). I would recommend 2^32 blocks as the limit for the
lifetime of a key, and that takes care of the 2^43/2^47 attacks as
well."

referring, although not by name, to both the birthday paradox and the differential cryptanalysis limits discussed above.  Keep in mind that at $2^{32}$ blocks, we are at a 39% probability of there being at least one ciphertext collision revealing some information.

Searching the archives for "birthday" also turned up some relevant messages, e.g. the relatively recent (21 April 2015) message  quoting the earlier message:

"> I think the main problem with 3DES is not that it is significantly slower
> than AES, but that it has blocksize of 64 bits, that is considered
> loo small for high-speed networks, when the possibility of birthday attack
> leads to necessity to frequently rekey.
It’s hard to make that case. The blocksize is 64 bits. So it’s prudent
to not use more than, say, a billion blocks. A billion blocks is 64
Gb. There are very few real tunnels that run that kind of throughput
in under a minute. OTOH it’s no problem at all to run a CreateChildSA
every minute, or even every five seconds. So I think there are very
few cases that *can’t* use 3DES."

This is interesting, particularly given its newness.  The author (Yoav Nir, one of the long-time leaders of the IPsec community) considers 3DES plus very frequent rekeying to be sufficient, at least for some use cases, and it's important for backwards compatibility.  However, in a slightly earlier (2012) exchange on the mailing list, David McGrew (another key IPsec person) and Nir covered the same issue, with McGrew arguing that no more than 50 megabytes should be encrypted with the same key even using 3DES, due to the birthday paradox.  McGrew went so far as to write up a 16-page analysis posted on the Cryptology preprint server (see references for more).

Looking Forward to Ramen Again

I can't claim to know much about the best ramen joints in the country. I'm a fan, but have no credentials as a connoisseur. But I do have a few favorite ramen joints I'm looking forward to visiting again when things ease.

• Tann-ya was probably the ramen joint that opened my eyes to the possibilities. It was also the first restaurant I ever knew of that had real-time online information about how long the line is -- being across the street from Tokyo Institute of Technology brings you a creative, technical clientele.
• Ichikanjin here in Kamakura makes a original, fresh take on ramen: tou-nyuu (soy milk) with crisp, sharply-flavored fresh vegetables on top. Walking distance from our current house.
• Yoshimura-ya, which anchors what we call "ramen intersection" in Yokohama.  Smoky flavor, and some fantastic, green not-really-garlic garlic, and a broth that you can watch being made in stages. The wait might be over an hour, so plan accordingly.  Has a Wikipedia page!
• Soranoiro with vegan ramen, though I'm a fan of having the crisp-fried cheese with it.
• Yabai Ramen is the opposite from Tokyo, but we'll go out of our way to eat there when driving through Odawara. (We've only eaten at Yabai, not its sister shop.)
• Tinnun in Jimbocho is maybe the farthest from traditional -- it's Thai style green curry ramen. I'm always jonesing for this.  Gotta go to the Jimbocho restaurant, it seems the other ones in this small Tokyo chain don't have the goods on this.
• Fuku-ya, a tiny local joint with good, well, they call it soba, but it's closer to ramen. Not a game-changer, but one of our local haunts. Their focus is about 50/50 on the noodles and on artisan sake they bring in from another prefecture, which interests me not at all. They're actually doing take-out during this episode, but we haven't ordered from them yet.
• Ramen Jiro. Of course. 'Nuff said.

There are many websites in both English and Japanese dedicated to the art of ramen. I should check them out, but I think I'd wind up walking to Tokyo and pounding on some doors and begging.

3.2 IKE and IPsec

(See the previous section or the top level if you're wondering what this is.)

If you really want to dig into the key exchange protocol, RFC 7296 (Oct. 2014) is the most modern reference.  Unless you're actually manually configuring or implementing the stuff, you probably won't care about the differences between it and the older versions.

https://tools.ietf.org/html/rfc7296

But you might want to start with RFC 4301 (Dec. 2005) (also a proposed standard), which is titled, "Security Architecture for the Internet Protocol."

IPsec has a couple of modes, but let's stick to what's called tunnel mode.  Two boxes, known as gateways, build one or more Security Associations (SAs). An SA describes which packets passing between the gateways are to be encrypted and how.  Those that are encrypted are encrypted in their entirety (packet headers and all), and sent as the payload of another IP packet, to be decrypted at the far end.  Tunnel mode is most often used to connect together via the Internet two networks (e.g., two offices of the same company) that are each considered to be relatively secure networks.  The packets between computers in one network and those in the other network are encrypted only during their transit from gateway to gateway.  Of course, these days, much (most?) data is also encrypted by the end hosts, especially for the two major applications of web and email, so much of the traffic in the tunnel will be double-encrypted.

The first SA created is the IKE SA itself, used only to carry the messages that govern the tunnel.  The first exchange of messages negotiates some security parameters, and carries random nonces used to "add freshness" to the cryptographic exchange and the parameters to be used for the Diffie-Hellman key exchange.  I believe this is where the preferred choice for the bulk encryption (3-DES v. AES v. whatever) is also negotiated.  Since we have not yet established the tunnel, these messages are necessarily sent as plaintext.

A block of material called SKEYSEED is calculated independently by both ends using the nonces generated by both ends and the shared secret generated by the Diffie-Hellman exchange in the INIT. Building SKEYSEED involves the use of a pseudorandom function (PRF) also agreed upon...in the first exchange?  I'm having trouble tracking where that's chosen.

SKEYSEED is used first to generate a key for the next message exchange, and then later to make keys for the Child SAs (below).

Next, there is an encrypted exchange that is used to authenticate the parties.  The authentication may be via an RSA digital signature, a shared (symmetric) key message integrity code, or a DSS digital signature.  In all three methods, each party signs a block of data using the secret, in a fashion that can be verified by the partner. (This could again be vulnerable to Shor's algorithm if it uses one of the public key methods, but keep in mind the messages containing this information are also encrypted; however, as we are just now

authenticating, it's possible that, up to this point, the partner at the other end of this connection is not who they claim to be!)

The IKE SA is used to create Child SAs, which carry the actual traffic.  The keys used for the Child SAs, therefore, are the obvious target for traffic-based attacks, though the real prize is the keys for the IKE SA.  I'm having a hard time imagining how to mount an effective attack against the IKE SA.

The key material for the Child SA is generated via a complex mechanism involving a new nonce and the PRF previously specified.  The initiator of the creation may also, optionally, specify that an entirely new Diffie-Hellman exchange be performed.  I'm very unclear on how often that option is used in practice.

Each SA, whether IKE or Child, can (and should) have a lifetime.  That lifetime can be specified in either seconds or in bytes that have been encrypted as they pass through the tunnel.  Once the lifetime has expired, the two gateways must create a new Child SA with new keys. This ultimately is the heart of what we're looking for here: what is that recommended lifetime today, and what should it be in the light of quantum computing?

3.1 Background on IPsec, IETF and RFCs

The Internet Engineering Task Force (IETF) is where protocol specifications for the Internet come from.  There is an entire Area within IETF (an "area" is the largest size organizational group in IETF, equivalent to a division of the American Physical Society, I would guess) dedicated to security, which charters many (more than twenty) different working groups.  Security is MUCH, MUCH MORE than cryptography, but

an important area of work is developing the network protocols that allow real systems to use the cryptographic techniques discovered by the mathematicians.  Moreover, theorists are inevitably naive about how much work it is to actually use their ideas.

https://trac.ietf.org/trac/sec/wiki

One of the most important means of securing your communications is IPsec, which builds a "tunnel" inside of which ordinary IP packets can be carried transparent to their origin and destination (meaning your laptop and the server don't have to be be configured to handle the encryption; they deal in unmodified, unencrypted IP packets) but protected as they transit public networks.

IPsec is complex and has been updated many times.  The Wikipedia page on it (which might be an easier entry point than the IETF indices, which are organized chronologically) lists over 40 standards-track documents, probably totaling over a thousand pages, some of which are outdated and some of which are still current.

https://en.wikipedia.org/wiki/IPsec

Those documents are what are known as RFCs, or Request for Comments documents.  They have different levels of authority, ranging from Experimental and Informational to Standard.  Reaching Standard can take decades and numerous iterations as the working groups gradually converge on what works in the real world, intersecting with what people will actually implement and use, but protocols are often de facto standards long before reaching that platinum frequent flyer status.

3.0 IPsec and the IETF

In this section, we return to the original question about rekeying that sparked this whole venture, and answer three questions:

1. What are the technical mechanisms in place for rekeying and effective use of encryption in the Internet standard security protocol IPsec?
2. What was known, at the time these protocols were developed, about the best practices for rekeying?
3. What are best practices today?

Next up: 3.1 Background on IPsec, IETF and RFCs

2.6: Notes & References

Some of the references I used for this section:

The Best Thing (TM):

https://sweet32.info/

https://sweet32.info/SWEET32_CCS16.pdf

https://danielmiessler.com/study/birthday_attack/

http://mathworld.wolfram.com/BirthdayAttack.html

1. Howard M. Heys, "A tutorial on linear and differential cryptanalysis", undated but probably 1999ish?

http://www.engr.mun.ca/~howard/Research/Papers/ldc_tutorial.html

2. Abdalla and Bellare,

https://link.springer.com/chapter/10.1007/3-540-44448-3_42

http://cseweb.ucsd.edu/~mihir/papers/rekey.html

found via

http://cseweb.ucsd.edu/~mihir/ 

That paper talks about differential/linear cryptanalysis and about the birthday paradox, saying block size $k$ needs to be rekeyed every $2^{k/2}$ blocks.

Bellare et al, A concrete security treatment of symmetric encryption:

analysis of the DES modes of operation

abstract from STOC 1997

https://ieeexplore.ieee.org/abstract/document/646128

full paper at

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.117.4734&rep=rep1&type=pdf

Focuses on DES, which was in the process of being superseded by AES even in 1997, but the content of the paper is valuable with respect to CBC.  I found the paper a tough read when trying to figure out how to apply the equations.

2.5: Known and chosen plaintexts in real systems

(I'm back, after a bit of a break. If you missed it, you can go back to the beginning of What Every Quantum Researcher and Engineer Should Know about Classical Cryptography.)

(Parts of this will make more sense after getting through the below. Maybe this section should be moved.  Also, some pictures will definitely help here.)

Modern HTTPS (web) and SMTP (email) connections have a lot of predictability in their content, with commands like 'HELO' and 'HTTP/1.1' being standard parts of an exchange.  We'll see in a later section more detail about how this encryption is done using a protocol called Transport Layer Security, or TLS, but for the moment we'll only focus on the message contents and the fact that they are pretty predictable.  Thus, it's reasonable to consider attacks on TLS to be known-plaintext attacks, and in fact there are cases where we can create chosen-plaintext attacks.

Consider, for example, the connection between your laptop and your email server, whether Gmail or your organization's server.  Assume that I, an attacker, can send you email and can observe your encrypted

connection to your server (perhaps I control a router somewhere between your server and your machine).  I can send you an email message that contains, for example, the strings 0x000000000000000 (15 zero bytes in a row) and 0x000000010000000 (with a one in the middle). If your cipher block size is 8 bytes, as in DES, I know that one of the encrypted blocks will be all zeroes and one will have exactly one bit set, even if I have trouble controlling the exact position within the overall stream.  I capture the ciphertext blocks, and compare them.  This single-bit difference between two blocks helps me with the attack.  All I have to do to execute a basic chosen-plaintext attack is to send you email and watch the resulting packets flow between your machines!

The success of such an attack requires a lot of assumptions about which parts of the entire process I can observe and which I can control, but using the principle of being conservative on security, assuming an attacker can force the choice of plaintext passed between two nodes through an encrypted connection is not unreasonable in today's richly interwoven distributed systems.

Especially for IPsec, there is another big vulnerability: one encrypted connection between two gateways (known as a Security Association, which we will see below) may carry data encrypted for a bunch of machines.  So if an attacker manages to install a program on only one laptop (say, via email, or while you're sitting at Starbucks), they can cause your system to send out arbitrarily chosen packets that will cross the tunnel, so they can execute a chosen plaintext attack pretty easily.  Since IPsec encrypts the whole packet, they may not be able to tell immediately which packets came from your laptop and which from a colleague's laptop, but that distinction is a relatively minor overhead.

Also, for every IP packet from your laptop to the email server passing through the IPsec tunnel, the IP header portion is going to be exactly the same, and its position in the encrypted stream is very easy to identify.  This led to some of the decisions around the use of CBC, I believe; I'm not aware of any deeper features intended to further obscure the location of such predictable data.

In short, as a defender, you should work on the assumption that a noticeable fraction of your plaintext is known under benign circumstances, and that it's not all that hard for an attacker to mount a chosen plaintext attack.

Moving Learning Online

We created an online course through FutureLearn a couple of years ago, for quantum computing:

https://www.futurelearn.com/courses/intro-to-quantum-computing

FL forced me to rethink how to learn online. It was a great experience. It was also a *tremendous* amount of work -- we spent *hundreds* of hours preparing the materials, shooting and editing the videos, doing the very limited amount of animations we did, prepping quizzes (creating effective multiple-choice quizzes is hard, and I don't think we've mastered it yet), developing JavaScript apps, making sure materials are accessible to the vision and hearing impaired, etc. It was more work than creating a classroom course, easily as much as writing a textbook, except that it involved a *team*, not just a solitary professor.

Obviously, this doesn't scale, in terms of faculty time, latency and university out-of-pocket costs.

We (Keio SFC) also have our "Global Campus" website, an archive of thousands (tens of thousands?) of hours of lectures, mostly in Japanese. Many of those are just videos of in-class lectures, many shared live at the time of recording with other campuses/universities (which was usually the incentive for recording them). They are a tremendous resource, but post-facto serve as the equivalent of a library of videotapes, rather than a true online learning experience that takes advantage of everything the Internet can be.

So, we need something in between: something that will allow us to quickly achieve a moderate but effective form of online learning: that engages students and keeps them engaged; that provides some form of interactivity and feedback to the students; that scales to working for hundreds of courses shifting online with a week's notice. What does that look like?

I've spent two years thinking about it, and I don't have an answer yet...

(Also, keep in mind as you move your courses online, that not all students have access to high-quality, high-bandwidth, unlimited-volume Internet.)

A Science Fiction Short Story: Quantum Computing for the Next Fifteen Years

(See the note at the bottom about hybrid algorithms!)

I started working on quantum computing full time in 2003, 17 years ago next month, after just shy of 17 years of working on classical networks, operating systems, and storage systems. Shor's algorithm and the basics of fault tolerance were known, but nobody really knew how to fit them together into a machine architecture; that was the theme of my Ph.D. thesis. Topological codes were just beginning to be developed, but were far from practical. HHL, VQE, QAOA and other algorithms didn't yet exist; indeed, the notion of hybrid algorithms didn't exist, to the best of my knowledge. Architecture-aware algorithm analysis began while I was doing my thesis, and to date my own biggest contributions may still lie there. Superconducting qubits existed, but just barely, and the transmon was still in the future. Many things that make CS theorists happy have happened, but that's outside my bailiwick.

Back around 2012, IARPA instituted a program to investigate algorithms at desirable problem sizes. They were:

1. The unique shortest vector (USV) problem, for a dimension of 50.
   
2. Linear systems of equations, with an array dimension of 3 × 108 .
   
3. The class number problem, for 124 decimal digits.
   
4. Ground-state energy calculation for an iron-sulphur molecular complex with 208 basis functions, to get 9 bits of accuracy in the result.
   
5. Quantum random walk on a binary welded tree, with a tree height of 300.
   
6. The triangle-finding problem on an arbitrary graph.
   
7. Boolean formula evaluation.
   

(Sorry, I seem not to have details on the problem instances for those last two.  See the supplementary material for our CACM article for some references, or my recent #QuantumComputerArchitecture tweetstorm and dig from there.) The early results from that suggested that at least the most straightforward implementations of those algorithms resulted in huge circuit depths, for some of the problems. This resulted in the first wave of pessimism, but since then we have had QAOA and a continuing wave of algorithms, small-scale implementations of existing algorithms, and software tools.

Periodically, anti-quantum computing pundits arise. They used to be of the "it'll never work" variety; these days it's usually of the "it's decades and decades away from being practical" kind. Rather than getting involved in "is not!" "is too!" arguments, I figured I'd just write down, off the top of my head, some the things that might happen in the next fifteen years, coming up to the 50th anniversary of Feynman and Deutsch:

• 2020-2022: First feedforward in solid state (superconducting?) systems, and with that the first claim of fault tolerance for a distance 3 surface code logical qubit. Similarly, [[7,1,3]] claim in ion traps. Solving of small problems on NISQ continues, in chemistry, graph states, quantum walks, etc. Improvements in software tools better support hybrid quantum-classical algorithms such as QAOA.  Fidelity and scalability of QFT remains a nagging problem, worse on some platforms than others. Quantum s*acy field quiet, as hardware focuses on measurement, feedforward, and continued improvement in CNOT gates. First wave of startup failures or bargain basement acquisitions, as VCs understand the technology and market better and focus on fewer but more promising companies.
• 2023-2024: First logical CNOT, using lattice surgery. Successful execution of graph and walk problems grow at better than hardware rates as compilers and use of QAOA and other techniques improves. Better techniques for extracting true answers out of noisy results help all algorithms. QFT works well now, thanks to very low-level implementations rather than gate-based. Renewed, incontrovertible claims of s*acy. New, wiser round of quantum software startups. First non-superconducting, non-ion trap, semi-commercial system. A handful of companies claim to be using quantum computers in production computing systems, but nobody really takes them seriously.
• 2025-2027: Error corrected systems start to open a serious gap in fidelity compared to physical qubits, but are still limited to 3-5 logical qubits and small code distances. NISQ optimization algorithms starting to be interesting, but are limited in data set size due to I/O and gates counts for dealing with heterogeneity. NISQ superconducting systems are bumping up against die size constraints; control bus limitations partially alleviated by cold stage control hardware. Multi-chip demonstrations exist, but are too slow and low fidelity to be practical. Ewin Tang's bombardment of the quantum algorithm ramparts begins to slow as we finally begin to grasp what's going to work well and what's not.
• 2028-2030: A 10-qubit QRAM appears, but it's specific to a particular technology and doesn't have an obvious path to scalability. Nevertheless, it's a game changer. Quantum volume of 10,000 reached, an important psychological and marketing threshold. It proves, in practice, to be more useful for deeper circuits on fewer qubits, rather than the other way around, so technically we're still well within classical simulation range. Large numbers of companies claim to be using quantum computers in production computing systems, and people take them quite seriously, but they don't really exceed classical capabilities yet. Quantum systems are indisputably generating new science.
• 2031-2035: The first serious hybrid-technology machines (deliberately discounting the use of photons here) appear, built from qubits sourced from multiple companies, another industry first. Multicomputer architectures, pioneered in practice in ion traps, become standard. SAT problems, not so different from those D-Wave originally proposed to solve, become all the rage as logical qubit counts reach 100. Quantum systems are indisputably solving problems important to commercial customers. As the first half century of quantum computing closes, classical supercomputing architects acknowledge that both Gustafson-Barsis's and Moore's Laws have stalled, apparently for good.

Remember, as America's foremost philosopher once noted, predictions are hard, especially about the future. With the American Physical Society's March Meeting coming up momentarily, it's especially risky, as there are often announcements there. Feel free to tell me I'm wrong about any individual point; I'll concede. I have very limited faith in all of this, but I do think the general direction is right.

(After I posted this, I got the following note from Peter McMahon about the history of hybrid algorithms. This early work deserves more attention than it gets!)

I wanted to bring to your attention some prior work that seems to be almost completely unknown in the QC community, but that brings the date of invention of hybrid algorithms for solving optimization problems to no later than 1999:

• "Quantum optimization" (Hogg, Portnov) https://doi.org/10.1016/S0020-0255(00)00052-9

• "Quantum optimization for combinatorial searches" (Trugenberger) https://doi.org/10.1088/1367-2630/4/1/326

I would argue that Eq. 1 of Hogg and Portnov’s paper, as well as their description of a hybrid approach to optimizing the phases at the top of Section 2.2, is capturing much of the core mechanism of QAOA, all the way back in 1999! The framing of applying evolution of the cost Hamiltonian isn’t quite there, but appears in Eq. 5 of Trugenberger’s paper. So between the two of these papers, we have the invention^ of hybrid quantum-classical optimization algorithms and the insight to use an alternation of mixing/driving and cost-function-Hamiltonian evolution in the quantum part of the algorithm.

^ Maybe there’s an even earlier paper presenting this kind of algorithm that I don’t know about; I’d be curious to learn about it if there is!

(Thanks, Peter!) 

New Factoring Record

After a quiet interval of just two weeks shy of a decade, on December 2nd the team of F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann announced a new record in factoring length, factoring a number created as part of the RSA Factoring Challenge.

This number is 795 bits, up from the 768-bit number successfully factored into its two prime factors back in December, 2009. In the interval, several other challenge numbers were factored, but each one was actually shorter than 768 bits.

What does this say about the strength of public-key cryptography? ...not much, in my non-expert opinion. An increase of 27 bits over a decade is, well, 2.7 bits/year. The authors estimate that their computation should be 2.25 times harder than the 768-bit number, based on scaling of the number field sieve.  However, various improvements gave them an advantage, and the 4,000 CPU-core years expended on this was 3 times faster than would otherwise have been expected.

In the prior decade, 1999-2009, the record was raised from 512 bits to 768 bits, over 25 bits/year. So this appears to be quite a slowdown, with the 768-bit record having held for an extraordinarily long time. But, among other things, the cash prize was withdrawn when the RSA Challenge ended in 2007, so incentives to simply demonstrate larger and larger factoring have declined. Of course, that doesn't mean that research on the topic has ended.

So, as always an important milestone, but hard to assign too much importance to it, either positive or negative, in my opinion.

Bill Manning

This morning I talked to Julie Manning, Bill's wife. Bill died early Saturday morning, at home in Oregon.  Most of you know Bill was waiting for a new heart. He would perhaps have gotten one next month. I guess the old one just wouldn't hold out long enough.

I first met Bill in about 1995, when I returned to ISI after my first stint in Japan.  He had taken a position in the Los Nettos project at ISI, a regional network project in the days when Internet service and operations work was still heavily shared between business and academia.  Bill brought an operator's eye to the project, often seeing things differently from the researchers in the group.

Bill kept the most erratic hours of any non-student I've ever met.  He might be in the office at 2am or at 2pm, either was equally likely. I'd ask, "Bill, what time did you come in?" He'd reply, "10am."  "I was here before that, and you were already here, it must have been earlier."  "Greenwich Mean Time."

And in one phase of life, "Bill, where do you live?" "Seat 4A."  He would speculate about his average altitude and speed over the previous month.

And, like any good geek, Bill had a spectacular collection of tie-dye t-shirts.  He came by the look honestly: growing up in the Bay Area, he had actually snuck into Grateful Dead rehearsals held in a barn, and had traveled as a deadhead for a while.

At ISI, we called Bill "the bad idea fairy".  He always brought a slightly-off-kilter view of technical problems, which triggered endless discussions of fascinating, if usually implausible, alternatives.

He had the most broad-ranging musical tastes of anyone I knew, and would eat almost anything (though, like me, he didn't drink alcohol). I was often envious of his eating and musical experiences.  He certainly lived life to its fullest.

On one occasion, I recall, we were eating lunch in a Thai restaurant for the first time.  Bill called for the food "the way you'd make it in Thailand".  The waiter went back into the kitchen and came out with a few raw Thai chiles.  Bill ate one whole, without even breaking a sweat.  The owner of the restaurant immediately came out to see who was eating them.  Pam became a friend to our group.

On other occasions, when the waiter asked for his order, Bill would point to another person at the table, and say, "I'll have what she's having."  "Well, what is she having?" "I don't know, I haven't heard her say."  Once in a while, he would point to someone else in the restaurant and say, "I'll have what they are having."  It was funny and sometimes disconcerting, which was very Bill, and it was also his way of making sure he himself was eating (and thinking and doing) as broadly as possible, without getting stale.

Bill worked in a bakery before joining Texas Instruments and accidentally falling into computer networking.  (When we first met, he was commuting between Houston and L.A.; Julie and the kids were still in Houston.)  I believe he attended a series of colleges but never finished his bachelor's degree.  Just a few years ago, however, Jun Murai convinced him to get a Ph.D.; this took clearing administrative hoops to demonstrate that Bill's life experience matched that of a bachelor's degree, which it certainly did.  I was honored to be on his Ph.D. committee.  I literally created a "trouble ticket" accounting scheme to track change requests for his thesis.

Bill was a valued member of the WIDE Project here in Japan.  He worked with the DNS root operations group here, and participated in as many WIDE meetings as he could.  He also came to Keio University's Shonan Fujisawa Campus when he was in Japan, and one of the best things about Bill was how seriously he took the students and their work, treating them like adult colleagues.

Bill had friends on all seven continents, and for all I know on the International Space Station, as well. He was loved by us all.

Julie does not plan to have a funeral immediately, so there is no need for flowers or the like. The family may do a memorial service in Utah in the spring.

He was a unique and wonderful human being. And a good friend.
Rest in peace, Bill.

Quantum Conference Calendars

For reference, here is a calendar for upcoming quantum workshops and conferences that seem to be kept up to date:

• Quantum Technology Lab

(n.b.: I had a bad calendar listed here! My apologies. Use the above one, which includes great info at the bottom about predatory publishers and conferences.)

2.4 Linear Cryptanalysis

Linear cryptanalysis (LC) is a known plaintext attack, developed by Mitsuru Matsui in 1990 after being inspired by differential cryptanalysis.  The key(!)  idea is to build a linear approximation of an S box, allowing you to calculate possible keys in reverse more quickly.

If a cipher is good, every individual bit of the output should have a 50% probability of being 0 and a 50% probability of being 1. Likewise, there should be no obvious relationship between the input and output bits (e.g., "If the third input bit is 1, the seventh output bit is 0.")  However, it is possible that some combinations of bits don't appear with equal probability. For example, the bit string composed of the first and third input bits and the second and fourth output bits should have all sixteen combinations 0000, 0001, ..., 1111 with equal probability, but perhaps there is a bias.  If $P_i$ is the $i$th input plaintext bit and $C_i$ is the $i$th output ciphertext bit, we can construct an equation like

$L = P_1 + P_3 + C_2 + C_4$

(where '+' is modulo 2 addition, or XOR, here).  We say that such a combination has a bias if the probability of $L$ being 0 is noticeably different from 50%.

Such a combination is a linear combination of bits.  It is known (by whom?) that if the S-boxes in our cipher are fully linear, then the cipher can be easily broken.  Therefore, designers always use nonlinear S-boxes, but some bias such as this may be discoverable.

The basic idea of LC, then, is to find such sets of bits that exhibit some bias and use some algebra to recover a few bits of the subkey used in the last round of the cipher, rinse and repeat.  The trick is to find the right relationships showing a detectable bias, as was done with differential analysis.  This is done by examining the math of the S-boxes in detail; as far as I can tell, this phase of the operation is done by very smart humans.

If you can find a combination with a bias of $\epsilon$, then you need $1/\epsilon^2$ plaintext ciphertext pairs to find some bits of the subkey.

This is done by taking multiple expressions like the above, combining them using Matsui's "Piling Up Principle" where you track the biases multiplied together to make a linear approximation of the nonlinear S-box.

With this linear approximation, it is possible to find correlations between the output of the next-to-last round of the cipher and the original input qubits, from which it is possible to recover information about the subkey used in the last round of the cipher.

Ultimately, this doesn't give you complete information about the key or the plaintext, but substantially reduces the work needed to find the full key by guiding a search, rather than just testing keys at random.

Linear cryptanalysis is considered to be a very general technique, but I don't see extensive attempts to apply it to AES.  Indeed, AES (which was developed in the 1990s from the proposed cipher known as Rijndael) was developed specifically with the idea of not being vulnerable to either differential or linear cryptanalysis.

I found Heys' tutorial to be clear and helpful in understanding LC.

2.3 Differential Cryptanalysis

(I'm back, after a bit of a break. If you missed it, you can go back to the beginning of What Every Quantum Researcher and Engineer Should Know about Classical Cryptography.)

Biham and Shamir wrote a seminal paper, then an easy-to-read book on their rediscovery of differential cryptanalysis.  The goal of DC is to recover the key used for a session, so it is potentially far more serious than the birthday attack.

The book says, "An interesting feature of the new attack is that it can be applied with the same complexity and success probability even if the key is frequently changed and thus the collected ciphertexts are derived from many different keys."  That's pretty alarming.  This appears in a paragraph discussing chosen plaintext, so it may be restricted to that case.  I infer from this that rather than needing the cumulative accretion of information, each trial is independent.

The attack works with either chosen plaintext, in which the attacker says, "Please encrypt this message for me, and give me the ciphertext," or known plaintext, in which the attacker knows that the message is a repetition of "HEILHILTER", as figured prominently in the cracking of the Enigma machine in WWII.  Modern HTTPS (secure web browsing) connections and SMTP (email) connections have enough predictability in their content to provide a similar fulcrum for such a lever.  There is a substantial difference in the complexity of the two attacks (see Tab. 2.1 in the book).  Known plaintext takes waaay more trials to succeed.

The key idea is the construction of differentials (hence the name) from specific S boxes.  Take two possible inputs to an S box, $X_1$ and $X_2$.  We can assume the subkey has been XORed into both $X_1$ and $X_2$ already.  $Y_1$ and $Y_2$ are the corresponding outputs of the S box.  We know that if $X_1 = X_2$, then $Y_1 = Y_2$ and also $X_1 + X_2 = 0$ (again, here '+' is addition modulo two, or XOR).

For the total encryption algorithm, changing one bit in the input should result in about half the output bits changing.  The S box should be similar; small changes in the input should mean large changes in the output.  In fact, the S box is small enough that we can exhaustively analyze its inputs.  We also know some rules that were chosen during the design phase, for example, changing one bit in the six-bit input should result in changes to at two bits in the four-bit output.

So a differential table for each S box is constructed by listing all $2^6$ possible XORs $X_1 + X_2$, and collecting the stats on $Y_1 + Y_2$.  From the differences found here, we can work backwards to find with "high" probability (slightly higher than completely random, at any rate) some characteristics of the outputs of the previous round.

The overall attack is performed by encrypting a bunch of randomly-chosen pairs of plaintexts (chosen as a pair; first a completely random one, then a second by XORing in a specific value) and comparing their ciphertexts until we find an output pair of ciphertexts that fit comfortably with the difference tables we have pre-computed for the S boxes.  Repeat until we have built up some statistics about the right set of bits in the output, and from that we can take a probabilistic guess at the subkey in the last round.  Based on that guess, we can narrow down the set of subkeys for the next-to-last round, rinse and repeat.  It's still a computationally intensive, tedious process, but much less than brute force.  Roughly, the probability of getting the ciphertext pairs we need is proportional to $1/p_D$, where $p_D$ is the differential probability in the table we are looking for, which may be quite small. (This seems to me that keeping a history of things you've already tried would increase the probability of finding a pair you like, so I'm still puzzled by the assertion above that this works even if the key is being changed frequently.)

Ultimately, this attack is considered practical against ordinary DES. Biham and Shamir estimated (p. 8, p. 61) that DES and DES-like systems, even with the full sixteen rounds, could be broken using $2^{43}$ to $2^{47}$ chosen plaintext/ciphertext pairs.  With 8-byte blocks, that's encryption of 64 terabytes up to a petabyte.  If the system under attack can encrypt a 40Gbps link at line rate, that's only a few hours up to a couple of days of data.

Triple-DES would be much, much longer, but 3-DES is still considered obsolete due to the birthday paradox attack above.  AES is stronger against DC, so this attack is of less help against properly-implemented, modern systems.

I know this is a very rough explanation; I have only a wobbly understanding of the process myself!  The differential tables are pretty straightforward, once you understand them, but working from there to a full-on attack is a big jump.

Favorite Books of the Last Decade

It seems the height of hubris to declare the "best books of the decade", when I read perhaps three hundred in that time span, while a couple of million books are published each year, most in languages I can't read. But at the same time, it's kind of nice to look back and think about which ones I read that have stayed with me. Most of these are pretty obvious choices; I don't think I'm saying much controversial here. Links go to my Goodreads reviews, where available, though most of the time I don't really write formal reviews. Also, note that this is books I read last decade, but many of the books themselves are older.

• Best General Science/Space History/Memoir: Lab Girl (previous decade: Riding Rockets; Honorable Mention: The Big Picture, We Have No Idea)
• Best Novel by a Nobelist: One Hundred Years of Solitude (Honorable Mention by a non-Nobelist: The Sea of Fertility)
• Best Whatever the Heck This Is: Self-Reference ENGINE
• Best IT-Related Nonfiction: Superintelligence (Honorable Mentions: The Codebreakers, The Book of Why, Quantum Computing Since Democritus, The Golden Ticket) Not without significant shortcomings, but a great springboard for conversation; there is also an even longer version of my review of this somewhere...
• Best Space Opera/Hard SF: Ancillary Justice (Very Honorable Mention: Three Body Problem)
• Best Cyberpunk: Daemon and Freedom(TM)
• Best Fantasy/Speculative Fiction: The Fifth Season
• Best History/Analysis: Why Nations Fail
• Best History/Big Picture Narrative: The Civil War Trilogy Apparently I didn't write a review, but I loved these books. Stiff competition from others on WWI, WWII, and topics such as the Crusades, the history of Islam, and the fall of the Ottoman Empire, though.
• Best History/Tight Focus: Hidden Figures
• Best Mystery: The City and the City
• Best Hard Boiled/Noir:  The Maltese Falcon (I enjoyed rereading my own review! I should put in the effort more often.)
• Best Collection: The Found and the Lost

I'm sure I'll come back to this at some point and go, "Geez, what was I thinking when I left out...?!?" but this short list will have to do for now!

Network Graph Visualization Software

Just a short list of network/graph visualization software we have used for various things. I keep losing track of them, so I figured it was worth writing them down.

• GraphViz is maybe the most venerable.
• NetworkX is a pretty cool toolkit for Python. Very easy to use, a great starting point.
• D3's Network Graph can do some nice things, well integrated into web pages.
• Graphs and Networks in Mathematica. I have used a couple of different approaches in Mathematica, including just treating the graph as a variable. I should dig out examples; I wasn't fully happy with what I managed with simple code. But if you're willing to go through the syntactic pain, you can do amazing things in Mathematica.
• OmNeT++ and ns-3 are full-on (classical) network simulators we have used for some sims, and they have built-in or add-on visualization tools.

Do you have a favorite or a dislike among this list? What have I missed?

2.2 Birthday Paradox, or, When Should I Change my Encryption Keys?

You're probably familiar with the basic idea of the birthday paradox: If you have $n$ people in a room, what's the probability of two of them sharing a birthday?  More concretely, how many people have to be in the room before the probability of two sharing a birthday exceeds 50%?  It's a surprisingly small number, but it's not a true paradox in the logical sense.  (This is also called the pigeonhole principle or hash collision probability.)

Modern ciphers are designed so that the ciphertext (output of the encryption) looks random; we can say that the ciphertext has very high entropy.  If the block size is $n$ bits, each of the $2^n$ possible bit combinations should be an equally likely result of encrypting a data block.  (The encryption is deterministic, but the output looks random.)

If we monitor a long stream of encrypted data, there is some probability that we will find two blocks that have the same ciphertext.  We call that a collision.  If the two blocks were encrypted with the same key, we gain information about the plaintext.

(Side question: How can you have birthday paradox collisions of the ciphertext?  Wouldn't that mean that the encryption process is lossy, and that it would be impossible to reliably decrypt that ciphertext back to both original blocks?

Answer: there is more information involved in both the encryption and decryption than just that specific block and the key.  This is the cipher block chaining mentioned at the end of Sec. 1.)

In CBC mode, what you gain is the XOR of two plaintext blocks.  If you get to choose which two, this could be incredibly valuable information; given that it's just two random blocks, it's less so, but not unimportant.  As it happens, if block numbers $i$ and $j$ have the same ciphertext $c[i] = c[j]$, then you get the XOR of the plaintext of blocks $i-1$ and $j-1$.

I spent quite a bit of time working through the math of the birthday paradox, only to come back to one of the first sources I found: the 2016 SWEET32 paper by Bhargavan and Leurent.  Sec. 2.2 of that paper has a compact description of the commonly-quoted square root limit, as well as why and how much to be conservative relative to that value.

If the block size is $n$ bits, there are $N = 2^n$ possible ciphertexts, and if the number of blocks encrypted is the square root of that number, $2^{n/2}$, the probability of at least one collision is above 39%, which arises in the limit as the expression $1-1/e^{1/2}$.  (See the appendix of these notes for some example calculations of this and the following to play around with.)

Assuming you consider a 39% chance of disclosing some information to be an unacceptably large probability, when should you rekey?  That's the first-level answer to our ultimate question of when to rekey using QKD, which is of course back where we started this conversation.  Say, for example, we want the probability of an attacker recovering a plaintext block using the birthday attack to be less than (for example) one in a billion.

If we have some power of two $D = 2^d$ ciphertext blocks, then the expected number of collisions is approximately $2^{2d-n-1}$.  For our one-in-a-billion probability, using $log_2(10^9) \approx 30$, we need to set up our session lifetime such that $2d-n-1 < -30$, or $d < (n-29)/2$.

Since DES has only a 64-bit block, we should set $d \le 17$.  That's a startlingly small number: $D = 2^{17}$ blocks and each block is eight bytes, so we should limit the use of a single key to one megabyte! An impractically small size.

If, on the other hand, you are okay with a disclosure probability of one in a million, we can raise that by a factor of a thousand and change keys once every gigabyte instead.  But if you are trying to protect a 40Gbps link -- a common backbone bandwidth today, and coming to the home in the foreseeable future -- that still means changing keys once every 200msec or so!

Ah, but AES uses $n = 128$, a block size twice as large.  Now we only need $d \le 49$ for that one-in-a-billion probability.  $D = 2^{49}$ times our block size of 16 bytes equals 8 terabytes, about 1,600 seconds on our 40Gbps link.  So change the keys at least once every half hour, and you're good.

Keep in mind a few points:

1. what's disclosed here is not the key but is plaintext-related, but not even pure plaintext; however, the insanely smart and devious cryptanalysts can do amazing things with small amounts of data;
2. this depends only on the block size of a block cipher, not on the key length;
3. part of this arises due to the CBC (cipher block chain) mode, but ECB (electronic code book) mode is worse; there are other modes that I haven't looked at closely; and
4. given that there are still other attacks, minimizing the amount of data under any given encryption key is still good practice.

Next, let's look at a couple of the cryptanalysis techniques.

(If you missed it, you can go back to the beginning of What Every Quantum Researcher and Engineer Should Know about Classical Cryptography.)

Quantum Information Theory, Computing, Algorithms, Networking, Engineering and Education Journals

(Edited on 20/2/29 and 20/5/19, as noted in line.)

The field of quantum computing, broadly constituted, is changing rapidly. Hundreds, nay thousands, of new people are entering the field each year right now. Eventually, things will settle out, but in the short run what is publishable research and how we publish it are going to undergo a lot of stress.  And eventually publishing will become less critical for a large number of quantum computing graduates, as they will move into the nascent quantum industry, where different metrics of success will be applied and ideas will affect society in different ways. But for now, the primary mode of work is research-oriented people creating and testing new ideas, and the standard approach to disseminating those ideas is peer-reviewed publications.

One of the problems is that architecture and engineering are neither theory nor experiment. Each is its own beast. Where do we send papers describing advances in software tools, architectural principles and evaluation, network protocols, etc.? Many of the existing journals are not good venues for this engineering-oriented work, but neither are most of the ACM and IEEE top journals and conferences.

Another item high on my list is how to value creation of new educational tools and techniques, e.g., our MOOC.

But before fussing too much, it's worth taking a look at what we currently have for publication venues...

Very roughly in terms of age, but grouped by organization (in short, the order in which my brain chose to produce/organize them of its own accord):

1. Nature and Science: You know the drill. Top experimental papers only. 20 papers/year each.
2. Physical Review Letters. Top papers, including theory and algorithms; HHL, for example. Highly compressed; I refer to a PRL as "the cryptographic hash of a longer paper still to come".
3. Physical Review A. Has been an excellent venue for almost anything quantum (my first quantum arithmetic paper, for example, and recent engineering-oriented work on quantum networks), and has explicitly added to its charter since the founding of APS's Division of Quantum Information, but is overwhelmed; acceptance rate is declining and topics are narrowing.
4. Physical Review X. Cody's architecture paper was explicitly described by the editors as, "Hey, this isn't really physics in the traditional sense, but we think it's cool." (Well, that's a liberal paraphrase.) (At almost 250 citations, according to Scholar, good call on their part if they value citations to their journal.)
5. IOP New Journal of Physics. An excellent venue, longer papers than PRL but good visibility. But seems to draw from same reviewer and reader pool as PRA.
6. IOP Quantum Science and Technology. Looks to be an excellent new venue, and quantum-focused, which is a win, and we're happy with it, but seems to draw from same reviewer and reader pool as PRA, at least so far. Hopefully engineering-oriented papers will continue to find a home here.
7. Quantum Information and Computation (QIC). Has been the journal of record for much quantum algorithms work, less so for experimental work and engineering. Subscriptions are expensive, but papers can be put on the arXiv.
8. Quantum Information Processing (QIP). Along with QIC, a top journal, with more experimental work. Also expensive, also arXiv-friendly.
9. International Journal of Quantum Information (IJQI). Gets less attention than QIC and QIP. Also arXiv-friendly.
10. ACM Journal of Emerging Technology in Computing Systems (JETC). One of my favorite journals. I spent two years as an associate editor, and wouldn't mind doing another stint here. arXiv-friendly. Not quantum only, but definitely has a good quantum component. Will be interesting to see if that changes with the introduction of...
11. ACM Transactions on Quantum Computing (TQC). If the quality of a review board is an indicator of the quality of a journal, destined to be the top thing in our field. True rock stars, and great breadth. Will probably be limited to a few dozen high-impact papers a year?
12. Nature Quantum Information (npj QI). Aims to be a top journal. Open access, which is great, but the author fees are outrageous. I won't pay them.
13. Nature Communications and Scientific Reports. In my limited experience, erratic in review quality and editorial procedures, and no help on formatting and copy editing, but still have the outrageous Nature open access fees. A worse deal all the way around than npj QI.
14. Science Advances. I haven't interacted with this yet at all. Also has high open access fees.
15. Quantum. The new star in our firmament. An overlay journal dependent on the arXiv. Outstanding, young editorial board, this is the cool coffee shop where all the hipsters hang out. Go here to be seen and to hear the newest tunes!
16. IEEE Transactions on Quantum Engineering. I have heard only rumors of this and either my Google-fu is poor, or there's nothing about it on the web. Could be good, but unless it's an exception to the truly egregious average IEEE journal latency, not useful for students. (Edit on 20/2/29: Link added. Erik DeBenedictis is EiC, the journal will be good! First papers published in early 2020.)
17. IET Quantum Communication is brand new, and has a lot of "wireless" in its call, since that's the community the founders come from.
18. PRX Quantum will start publishing in mid-2020 (Edit: this one added 20/2/29.)
19. Wiley Quantum Engineering (Edit: this one added 20/2/29.)
20. Springer Quantum Machine Intelligence (Edit: this one added 20/5/19.)

Of course, there are conferences and workshops, too.

And I'm working on a short slide deck on how contributions to open source and non-traditional publishing (e.g. my #QuantumComputerArchitecture tweetstorm) should count.

But for the moment, the above nineteen or so journals are where the primary action is.

2.1.2 Diffusion and Confusion

Claude Shannon, in his seminal article on the mathematics of cryptography, defined two concepts he called diffusion and confusion.  In diffusion, information from the original plaintext message is spread across more than one symbol in the output ciphertext; the farther the information spreads, the better.  Shannon defined confusion as making "the relation between...[the ciphertext] $E$ and the...[key] $K$ a very complex and involved one."

Feistel, who designed DES, called diffusion the avalanche effect. Webster and Tavares defined the strict avalanche criterion (SAC), requiring that changing a single input bit flips each of the output bits with 50% probability.

The Handbook of Applied Cryptography says the following (p. 20 in my edition):

A substitution in a round is said to add confusion to the encryption process whereas a transposition [permutation] is said to add diffusion. Confusion is intended to make the relationship between the key and the ciphertext as complex as possible.  Diffusion refers to rearranging or spreading out the bits in the message so that any redundancy in the plaintext is spread out over the ciphertext.

I haven't seen it written quite this directly (but then, I'm not that well read in crypto), but I think it's fair to say that confusion is achieved by the nonlinearity of the S-boxes.

These two concepts don't seem to figure prominently in the cryptography books and papers I have been reading, but it seems to me that they ultimately underly much of the process of cryptanalysis: spreading data broadly reduces the relationship exhibited by two ciphertexts even when the plaintexts are closely related, expanding the search space; and the nonlinearity means that even a large set of straightforward equations is not enough to simply and mathematicallyrelate the input and output.

2.1 Playing Defense / 2.1.1 Entropy

2.1.1 Entropy

The single most important concept in cryptography -- indeed, in all of information theory, and inarguably one of the most important in all of computer science -- is Claude Shannon's entropy.  The entropy is, roughly, the amount of disorder in a sequence of data, or the amount of information that must be transmitted to reconstruct the data.  When the entropy of a cleartext message is high, it is hard to predict the next symbol (bit or byte or letter or floating point number); purely
random data has very high entropy.  When it is low, the cleartext has a skewed probability distribution such that, e.g., the letter 'e' or the number 0 is more common than other values.

Of course, because encryption tries to hide information, encrypted data looks as random as possible: it has very high entropy.  Thus, an easy way to automate a test to see if we have successfully decrypted a message is to calculate the entropy of our provisionally decrypted plaintext; low entropy indicates a high probability that we have (at least partially) succeeded.

The entropy is defined as

$H_{2}(X)=-\sum_{i=1}^{N} \frac{\operatorname{count}_{i}}{N}\log_{2}\left(\frac{\operatorname{count}_{i}}{N}\right)$

where $\operatorname{count}_i$ is the number of times that the $i$th value appeared in our data, and $N$ is the number of different values that show up in our data sequence.

From the fantastic website RosettaCode.org, we have a simple example in Python of calculating the entropy in bits per byte:

import math from collections import Counter def entropy(s): p, lns = Counter(s), float(len(s)) return -sum( count/lns * math.log(count/lns, 2) for count in p.values()) entropy("1223334444")

(This function can actually calculate entropy of strings of other types besides characters, as well.)

Note that this definition of entropy does not take into account any long-range structure; it is purely based on the overall probability of the appearance of a given set of symbols.  Thus, to this function, the strings 0101...01 and 000...01...111 have a bit-level entropy just as high as a string composed of exactly 50/50 randomly chosen 0s and 1s, although by applying a little intelligence we can easily reconstruct the former but not the latter (at least, not exactly).  Many lossless data compression programs operate on stateful _sequences_ of data to predict the next symbol.  For example, the common Unix utilities gzip and compress use the Lempel-Ziv algorithm, which builds a dictionary of sequences as it goes, so that repetitive data and long runs are compressed effectively; this is especially good at sequences such as 0101...01 or 000...01...111.

(Taking still further advantage of brainpower, the ultimate in compression is measured using the _Kolmogorov complexity_: the length of the shortest program that will reproduce the sequence.  This has very low complexity for anything highly regular, as well as seemingly irregular sequences such as the output of a pseudo-random number generator or the digits of $\pi$.  I am not aware of any automated form for calculating the Kolmogorov complexity of an arbitrary sequence of data.)

This, obviously, is one of the motivations for the substitution phase in a substitution-permutation network; with permutation only the entropy of the original cleartext is preserved in the ciphertext, and in some cases reveals a great deal about the original data.