The NSA Tentatively Rejects Quantum Key Distribution Protocols

08 September 2023

In our imperfect world filled with bad actors, the need for secure data transmission is plain. For this reason alone, the search for better security measures is always afoot, and many times quantum protocols are boldly cited as the future of encryption and security (especially by science popularizers). This may very well be true, but there is still a lot of ground to cover before we get there (and I'd be remiss not to mention that quantum protocols do nothing to prevent harvest now, decrypt later attacks). Still, it is true that quantum key distribution (QKD) protocols are information-theoretically secure (meaning they are immune to attackers with unlimited computational power), whereas all classical and post-quantum protocols are only as secure as our beliefs in many complexity-theoretic hardness conjectures to do with problems like factoring or ring learning with errors (RLWE).

Recently, the NSA (famous for being the only government agency that listens to the people (joke!)) published a web article detailing why they think quantum key distribution (QKD) and quantum cryptography (QC) are not suitable for "securing the transmission of data in National Security Systems".

Their argument cites five limitations, to which there is a great rebuttal by Renner and Wolf on the arXiv that I feel does a good job detailing why the NSA might be a bit premature to entirely dismiss this technology today (in fairness, however, the NSA does say that if the five limitations can be overcome, then the technology should be reconsidered). Here are the limitations they cite, together with my immediate thoughts (informed by the Renner and Wolf paper):

Limitation 1: "Quantum key distribution is only a partial solution. QKD generates keying material for an encryption algorithm that provides confidentiality. Such keying material could also be used in symmetric key cryptographic algorithms to provide integrity and authentication if one has the cryptographic assurance that the original QKD transmission comes from the desired entity (i.e. entity source authentication). QKD does not provide a means to authenticate the QKD transmission source. Therefore, source authentication requires the use of asymmetric cryptography or preplaced keys to provide that authentication. Moreover, the confidentiality services QKD offers can be provided by quantum-resistant cryptography, which is typically less expensive with a better understood risk profile."

First of all, and this is underscored by Renner and Wolf, who ever said that QKD would solve authentication? Surely to authenticate anything requires a preshared something (or a trusted third party) to do the authentication! If there is nothing preshared, then how can anyone know if the message they receive is from the right person or not? Of course, there are classical key exchange protocols like Diffie-Hellman that are non-authenticated, but my understanding is that this forms the basis of a later authenticated protocol. Perhaps the critique by the NSA is there is no obvious Diffie-Hellman-like non-authenticated quantum protocol? Still, I don't feel that this is really a quantum problem.

Secondly, as I said above, post-quantum cryptography relies on hardness conjectures in complexity theory, whereas QKD is provably informationally secure. Surely that means its risk profile is better understood?

Limitation 2: "Quantum key distribution requires special purpose equipment. QKD is based on physical properties, and its security derives from unique physical layer communications. This requires users to lease dedicated fiber connections or physically manage free-space transmitters. It cannot be implemented in software or as a service on a network, and cannot be easily integrated into existing network equipment. Since QKD is hardware-based it also lacks flexibility for upgrades or security patches."

Come on. This is a new technology, and that by definition means new software and hardware is needed to implement it. It's not something we can just get for Christmas, we need to build it, and the same was true for the computers we use today to do encryption: we had to build it. So yes, the infrastructure for classical cryptographic protocols is already there, but it wasn't 100 years ago. 100 years from now, I see no reason why the cryptographic protocols in place then must be the same as they are now. That said, I do get that in the near term QKD is not going to be used because of technological limitations. But everyone knows that (I hope!).

Limitation 3: "Quantum key distribution increases infrastructure costs and insider threat risks. QKD networks frequently necessitate the use of trusted relays, entailing additional cost for secure facilities and additional security risk from insider threats. This eliminates many use cases from consideration."

I think in the near-term this is true, in part because unlike classical repeaters which first measure an incoming signal, copy it, and then send it along at a higher power, quantum repeaters must operate differently, as they cannot copy their input thanks to the no-cloning theorem. A quantum repeater is necessary, particularly if we store the quantum information in photons and transmit it via fiber optic cables, because the transmittance of a lossy bosonic channel scales like \[e^{-L / L'}\], where \[L\] is the length of the cable and \[L'\] is its attenuation distance. Thus, the most obvious solution is to have trusted relays, which, as the NSA says, would indeed be costly and introduce insider threats. However, as described in this review article on quantum repeaters, there is good work on quantum repeaters that would completely boot the need for trusted relay stations. I don't know what the state of the art is here, but I would bet that with the technology to do faithful QKD on short distances, we would pretty quickly come to the technology to do implement quantum repeaters.

Limitation 4: "Securing and validating quantum key distribution is a significant challenge. The actual security provided by a QKD system is not the theoretical unconditional security from the laws of physics (as modeled and often suggested), but rather the more limited security that can be achieved by hardware and engineering designs. The tolerance for error in cryptographic security, however, is many orders of magnitude smaller than in most physical engineering scenarios making it very difficult to validate. The specific hardware used to perform QKD can introduce vulnerabilities, resulting in several well-publicized attacks on commercial QKD systems."

I feel this is a good point, and don't have too much to say about it. It seems right to me that we will never perfectly implement any QKD protocol, and thus there will always be side channel attacks. Therefore, recurring security patches will still be necessary, and they will plausibly be very intricate.

Limitation 5: "Quantum key distribution increases the risk of denial of service. The sensitivity to an eavesdropper as the theoretical basis for QKD security claims also shows that denial of service is a significant risk for QKD."

This is true, basically because of state collapse. However, it assumes a point-to-point communication scheme. As Renner and Wolf correctly point out, if the scheme is not point-to-point but instead redundantly distributed over a network, then this is a non-issue. In their words, "this is not a problem that is intrinsic to QKD. Instead, it is a consequence of the high price tag of quantum communication technology, which currently prevents us from building quantum networks with many links"

All-in-all, I'm not on the same page as the NSA regarding this technology, at least in the semi-long run. Sure I buy all their arguments regarding the use of QKD in, say, the next five to ten years. But who knows where quantum technology will be in the future. Maybe it will be ubiquitous as the quantum over-hypers say, in which case I'll have a good job, or maybe it won't, and I'll be on the street somewhere. Time will tell.

ChatGPT Flunks Physics Diagnostic

02 September 2023

My TA duties at CU Boulder began last week, and with the looming possibility that some of my students might use ChatGPT on homeworks, I was curious how well it would do on the diagnostic test all general physics 1 students must take at their first recitation section. For reference, I'm pretty sure all these questions are adapted from McDermott and Shaffer's Tutorials in Introductory Physics.

tl;dr: Of the six questions I asked ChatGPT, it got one (yes one!) right. It kind of got a third of Question 4 right, so if we're generous let's say \[1/6 + (1/3)/6 = 2/9\] of the questions right, so roughly a \[22\%\] overall.

Note: This is GPT 3.5. GPT 4 might do better, but I'm on a budget. Also, I am not the best prompt engineer, and I did not ask ChatGPT to exhibit chain-of-thought reasoning, which studies have shown actually improve LLMs. I am merely asking the questions as the students see them, more or less. The only difference is ChatGPT doesn't get a picture of the situation, but I feel I do a good job describing it, and I feel ChatGPT describes it well back to me. So I take it ChatGPT understands the physical situation.

Here goes:

Matthew: Imagine a strobe diagram of a ball with some initial, finite velocity moving up an infinitely long ramp that is at an angle between 0 and 90 degrees from parallel to the ground. Say "good" if you understand and "not good" if you do not understand.

ChatGPT: Good. I understand that you're describing a situation where a ball with an initial velocity is moving up a ramp at an angle between 0 and 90 degrees from parallel to the ground, and you're asking me to imagine a strobe diagram of this scenario. In a strobe diagram, you're essentially looking at snapshots of the ball's motion at specific time intervals to understand how its position changes as it moves up the ramp.

Matthew: Right, now for some questions.

ChatGPT: Of course! Feel free to ask any questions you have about the scenario or any related concepts. I'm here to help!

Matthew: Question 1: When the ball is moving up the ramp, in which direction does the acceleration vector of the ball point?

ChatGPT: When the ball is moving up the ramp, the acceleration vector of the ball points both up the ramp and perpendicular to it. This is because the ball is moving against the force of gravity, which tries to pull it down the ramp, and the normal force from the ramp provides the perpendicular component of the acceleration. So, the acceleration vector has both a component pointing up the ramp (parallel to the surface) and a component perpendicular to the ramp (normal to the surface).

Matthew: So in which direction is the *net* force, relative to the ramp?

ChatGPT: The net force on the ball is directed along the ramp. It's important to note that the net force includes both the force due to the component of gravity parallel to the ramp (which tries to pull the ball downward) and any additional force applied to the ball or provided by the ramp itself. The net force is responsible for the ball's acceleration along the ramp's surface.

Matthew: Up or down along the ramp?

ChatGPT: I apologize for any confusion. The net force on the ball, when moving up the ramp, points up along the ramp. This net force is the vector sum of the component of gravity pulling the ball down the ramp and any other forces that might be acting on the ball in that direction. The net force's direction determines the ball's acceleration up the ramp.

Matthew: Question 2: When the ball reaches its apex on the ramp, in which direction does the acceleration vector point (again, relative to the ramp)?

ChatGPT: When the ball reaches its apex on the ramp, the acceleration vector points directly downward, which is perpendicular to the ramp's surface. At the apex, the ball has momentarily stopped moving upward and starts to reverse its direction and move back down the ramp due to the influence of gravity. The acceleration vector always points in the direction of the net force, and at the apex, gravity becomes the dominant force causing the ball to accelerate downward.

Matthew: Question 3: When the ball reaches the point as in Question 1, but this time when the ball is rolling down the ramp, in which direction does the acceleration vector point (again, relative to the ramp)?

ChatGPT: When the ball is rolling down the ramp, the acceleration vector points down along the ramp, in the same direction as the ball's motion. In this scenario, the force of gravity is aiding the ball's motion down the ramp, so the acceleration vector is in the same direction as the motion. This is unlike the situation when the ball was moving up the ramp, where the acceleration was against the direction of motion.

Matthew: Question 4: Explain the reasoning you used to obtain the direction of the acceleration of the ball at each location in the above three questions.

ChatGPT: Certainly, here's the reasoning for each of the scenarios:

Question 1 (Ball moving up the ramp): When the ball is moving up the ramp, its velocity is directed up the ramp, but it's slowing down due to the net force (which includes the component of gravity down the ramp and any other forces). The net force is directed opposite to the motion of the ball, which means the acceleration is also opposite to the motion. Therefore, the acceleration vector points up the ramp, opposite to the velocity vector.

Question 2 (Ball at the apex of the ramp): At the apex of the ramp, the ball momentarily stops moving upward and starts to reverse its direction due to the force of gravity pulling it downward. The net force, and therefore the acceleration, points straight downward (perpendicular to the ramp's surface), causing the ball to start moving back down the ramp.

Question 3 (Ball rolling down the ramp): When the ball is rolling down the ramp, its velocity and the direction of motion are both down the ramp. The force of gravity is aiding the ball's motion in this direction. The net force, and hence the acceleration, is also directed in the same direction as the motion, down the ramp, due to the gravitational force helping the ball's downward movement.

In all these cases, the direction of the acceleration is determined by the net force acting on the ball, which in turn affects how the ball's velocity changes.

Matthew: Question 5: How does the magnitude of the acceleration change as the ball moves uphill?

ChatGPT: As the ball moves uphill, the magnitude of the acceleration decreases. This is because the force of gravity is acting against the motion of the ball, and as the ball moves further up the ramp, the component of gravity pulling it back down the ramp becomes stronger relative to the net force causing it to move up. As a result, the ball's acceleration decreases, and it slows down in its uphill motion.

At the highest point (apex) of the ramp, the ball's velocity momentarily becomes zero before it starts moving back down due to the increasing influence of gravity. At this point, the acceleration is at its lowest magnitude, and then it gradually increases as the ball begins moving back down the ramp and gravity aids its downward motion.

Matthew: Question 6: How does the magnitude of the acceleration change as the ball moves downhill?

ChatGPT: As the ball moves downhill, the magnitude of the acceleration increases. This is because the force of gravity is aiding the motion of the ball in the direction it is moving, which is down the ramp. As the ball moves further downhill, the component of gravity pulling it in the same direction as its motion becomes stronger, resulting in a larger net force and therefore a higher magnitude of acceleration. The ball accelerates more and more as it moves further downhill.

In summary, when moving downhill, the ball experiences an increasing magnitude of acceleration due to the gravitational force helping its motion in the same direction as the ramp.

Matthew: Okay, you got a 1/6. But that's okay! It's the beginning of the semester! Make sure to attend class.

ChatGPT: I apologize for any confusion or misunderstanding in my previous responses. Thank you for your understanding, and I appreciate the feedback. If you have any more questions in the future or if there's anything else I can assist you with, please don't hesitate to ask. Good luck with your studies, and remember, I'm here to help whenever you need it!

I Hope Mars is Dead

26 August 2023

One of my favorite contemporary philosophers, Nick Bostrom, once wrote the captivating paper Why I Hope the Search for Extraterrestrial Life Finds Nothing. After reading both Max Tegmark's Our Mathematical Universe and Paul Davies The Eerie Silence, I have joined Bostrom's seemingly contrarian camp.

To assign credit where credit is due, however, this view is not Bostrom's idea. Rather, it originates from Robin Hanson's Great Filter, which is a possible resolution to Enrico Fermi's eponymous paradox: if life is so easy, then where are all the aliens?

According to the GF, even if abiogenesis is easy, then there is plausibly some extremely unlikely event between abiogenesis to the "techogenesis" of a species as, or far more, technically literate as our own. Indeed, on Earth a lot had to happen before the most primitive prokaryotes evolved enough to send a descendent to the moon. Perhaps one of those events, such as the evolution of multicellular eukaryotes, is the impossibly lucky roll our great ancestors had. Of course, who's to say there aren't many GFs?

It is self-evident, I think, that just because the descendents of some extremely primitive prokaryotes sent a man to the moon, it does not imply that a later descendent of us humans will be sent to another galaxy. We know this because we humans are far from this, and we don't seem to be much closer as the years go by. But of course I hope, one day, we will be there.

This hope of an awesome, space faring civilization is at the center of Bostrom's argument. However, because we're not there yet, it raises the question of whether we ever will be. Is there another GF between where we humans are now and the time when humans could be a space faring civilization, where we colonize planets like in The Expanse? What would such a GF look like? If you think about it, a GF is really just a euphemism for an existential risk. In this vein, Bostrom writes:

Perhaps the most likely type of existential risks that could constitute a Great Filter are those that arise from technological discovery. It is not farfetched to suppose that there might be some possible technology which is such that (a) virtually all sufficiently advanced civilizations eventually discover it and (b) its discovery leads almost universally to existential disaster.

Where, then, is the GF? We hope it's behind us, so that laid before us is a more or less existentially risk free future where the path to a space-based future is not improbable. But how can we reason about this? No one knows for sure, but we can put on our Bayesian hats and see what comes out.

Let \[P(\text{GF is at or before }t)\] be the probability that the GF is at or before some "time" \[t\], where \[t\] is simply a placeholder for some epoch making event that is plausibly necessary to become space faring, such as the transition from single- to multicellular organisms, or the harnessing of nuclear energy (or maybe, even, discovering to effectively control AI).

How can we estimate \[P(\text{GF at or before }t)\] given the observations of life that we can do today. Well, absent any radio signals from intelligent species, let alone in-person "hellos" from already space faring civilizations, the best we can do is look at ourselves, as well as the planets and moons and other natural satellites in our solar system. Following Bostrom, let's take Mars as our case study.

Suppose we think the GF is near some time \[t = t'\], so that the probability distribution \[P\] is somewhat peaked around \[t'\]. And now consider what happens if on Mars we were to discover a lifeform, independent of all life on Earth, at the stage \[t'\]. What happens to the distribution \[P\]? Well, simple Bayesian updating tells us that \[P(\text{GF at or before }t') \mid \text{Mars data})\] equals \{\frac{P(\text{Mars data} \mid \text{GF at or before }t')P(\text{GF at or before }t')}{P(\text{Mars data)}}.\} But because we thought the GF was at \[t'\], then, by definition, \[P(\text{Mars data} \mid \text{GF at or before }t')\] is an extremely small number, much smaller than the other probabilities in this equation. The net effect, then, is to lower our credence that the GF is actually at or before time \[t'\], and must instead be later.

So you see, the more advanced species we discover independent of ourselves, the more the GF is shifted to the future. The best way to keep the GF in our past, then, is for all searches for extraterrestrial life to turn up empty handed.

To give the final say to Bostrom:

So this is why I’m hoping that our space probes will discover dead rocks and lifeless sands on Mars, on Jupiter’s moon Europa, and everywhere else our astronomers look. It would keep alive the hope for a great future for humanity.

The Matterhorn is Beautiful, from Afar

21 July 2023

On July 7th this year, my long time friend and climbing partner David Sobek and I summited Mont Blanc (4807 m / 15780 ft). To keep things interesting, and because we were feeling "traversy", we opted to ascend via the Trois Monts route and then descend via the Goûter route (i.e. the standard route). This is the mountaineers' way from Chamonix to Les Houches.

Trois Monts is awesome, in part because in addition to Mont Blanc, you flirt with the summits of Mont Blanc du Tacul (which David and I summited a few days prior to acclimate and to also test our mixed climbing abilities) and Mont Maudit. Indeed, this turned out to be a great, albeit long day. Leaving the Cosmique hut at midnight was a magical start, especially with the bright moon and the all-satisfying crunch of good snow beneath our crampons.

David took the lead on the way up, and man was he strong. I felt like I was being pulled at times. This became especially apparent at around 4500 m, where after downing a salt stick I started to feel a little nauseous. Shortly, though, we made it to the summit, where we took an obligatory photo:

(Notice my frozen water tube and also the Matterhorn in the background.) Then, we headed down what I hope to never have to head down again, the Goûter route. It's not that it's technical, it's just very long. And tedious. And my semi-stress-fractured foot was hurting in my mountain boots. And did I mention that it was tedious? We made it though.

All-in-all, 11 hours, 9 minutes, and 19 seconds from Cosmique to the train at the base of the Goûter route. Next time, to avoid things like the Death Couloir, I'll just go down Trois Monts (perhaps with a Beal Escaper to efficiently rap the steep snow crux on Mont Maudit). Back in Chamonix, we grabbed a beer, had some food, checked weather, and decided we wanted some more.

So, two days later, I find myself with a family size Toblerone chocolate bar in my alpine bag, while organizing my gear in the Hörnli hut right below the Hörnli ridge of the Matterhorn. The next day, we set off at 3:30 am up one of the most iconic peaks in the world.

It sucked. It sucked in a way that even after it sucked. Not quite full on Type 3 fun, but, say, Type 2.5. Actually that's too generous. 2.73 is more like it. Suffice it to say, I'll never do it again, at least never again without a guide. It is a taxing, ten hour chossy scramble. Beautiful views, yes, and pulling up onto the Swiss and Italian summits was amazing. Here's a photo of us essentially on the summits:

But gosh is it a heinous climb. So much attention was required for each step that I have never been more mentally drained by a climb. The whole day, the words of Edward Whymper in his Scrambles Amongst The Alps echoed in my head: "Climb if you will, but remember that courage and strength are nought without prudence, and that a momentary negligence may destroy the happiness of a lifetime. Do nothing in haste; look well to each step; and from the beginning think what may be the end."

Anyway, I'm happy we made it. I'm happy to say I've climbed the Matterhorn. And I'm happy I learned a bit about myself that day, and also about my climbing relationship with David. But boy is that an ugly mountain. David and I met some lively Czech climbers on the summit and they also agreed: the Matterhorn is best viewed from afar. Too close, and its beauty decays to choss.