In 2004, I placed a bet with NSA's Art Drisko, coming due in 2024. Prize: $20. My bet: JPEGs continue to display just fine in browsers, automatically (no browser configuration needed), in 2024. His bet: They don't.
(For some reason, NSA hasn't been answering my email for a few years. Maybe they haven't been receiving it?)
In 2014, I placed a bet with Antoine Joux, coming due in 2032, about the factorization of RSA-2048, specifically the RSA-2048 challenge number issued by the RSA company in 1991. Prize: a 700ml bottle of (at least) 18-year-old single-malt scotch (aged properly, of course; buying 6-year-old scotch and letting it sit on the shelf for 12 years doesn't qualify). My bet: the RSA-2048 challenge is publicly factored first by quantum computers. His bet: the RSA-2048 challenge is publicly factored first by non-quantum computers. If the challenge isn't publicly factored by 2032, the bet is off.
At Latincrypt 2017, I placed a bet with Francisco Rodríguez-Henríquez, coming due at Latincrypt 2033, also about the RSA-2048 challenge. Prize: $2048. My bet: the RSA-2048 challenge is publicly factored by a quantum computer before the bet comes due. His bet: It isn't. (I would have been happy to bet on 2032 again, but Latincrypt is only every second year.)
If I win all three bets (at this point I'm 99% sure that I'll win the first one, although I'm less sure that I'll be able to collect my winnings), it'll be obvious to everybody that $2048 represents only a tiny fraction of the tremendous damage to information security caused by quantum computers. We'll all see the factors of the RSA-2048 challenge announced by Google or IBM or whoever else manages to win the public race. Presumably the same techniques would have been able to factor any RSA-2048 public key. Presumably large-scale attackers would have already secretly developed the same capabilities years earlier, and would have refined those capabilities to run faster and with lower cost.
We don't know that this will happen. Maybe quantum computing will run into an insurmountable obstacle, or will take longer than 2032. What we do know, what we've already known for years, is that large-scale attackers are already recording as much Internet traffic as they can. Do they throw the data away if it's encrypted with RSA-2048? Of course not. They keep it forever, hoping and expecting that someday they'll develop the ability to decrypt it, for example by building a quantum computer.
I don't see how we can stop large-scale attackers from building quantum computers. We can, however, take action aimed at reducing the damage that those computers will cause. There are already many proposals for what cryptography will look like after quantum computers: post-quantum encryption systems that we can use instead of RSA or elliptic-curve cryptography to encrypt our data. The serious proposals already work on our current computers. That's why Google was already able to roll out an experiment with post-quantum cryptography starting almost six years ago, July 2016:
Today we're announcing an experiment in Chrome where a small fraction of connections between desktop Chrome and Google's servers will use a post-quantum key-exchange algorithm in addition to the elliptic-curve key-exchange algorithm that would typically be used.
You already know what happened next. This experiment, CECPQ1, was successful, showing that HTTPS can easily afford post-quantum cryptography. This rapidly snowballed into successful wide-scale deployment of post-quantum cryptography: Google extended the experiment to all Chrome connections, and the rest of the industry soon followed. There's nothing we can do retroactively about many years of earlier RSA-2048-encrypted traffic already stored by attackers, but we've all been comfortably using post-quantum cryptography for years now.
Wait, no, that isn't what happened next. Yes, the CECPQ1 experiment was successful, showing that HTTPS can easily afford post-quantum cryptography. But this didn't snowball. Google turned the experiment off within a few months. People with the ability to deploy post-quantum cryptography suddenly seemed scared to do so. Eventually Google started an ntruhrss701 experiment and OpenSSH integrated sntrup761, but these steps have been slow and tentative. The bottom line is that there were years of delay of post-quantum deployment, years of additional traffic being handed over to the attackers.
Why did that happen? Let's take a closer look.
Most companies, even companies with tremendous expertise in software engineering, are justifiably afraid to touch cryptography. Even if there's a plug-and-play software library that advertises exactly the right features, how do these companies evaluate whether the library is secure? There's a steady drumbeat of news articles shaming companies for deploying broken cryptography and pointing to explanations of how the cryptography failed, explanations relying on arcane cryptographic details that most companies would never have thought to check.
So most companies have strong incentives to wait for cryptographic standards. A standard instantly changes the company's thought process: "There's a standard from NIST saying that this cryptography is safe, and the library says it's implementing this standard, and we can easily check that the library is correctly computing the test vectors shown in the standard. If anything goes wrong, we'll be able to blame NIST for its deficient standard."
But the picture is different for the occasional companies responsible for the bulk of cryptographic deployment today. These companies hire cryptographers, and send people to conferences on cryptography, and are constantly touching cryptography without waiting for standards. Apple didn't wait for NIST when it rolled out X25519 for new iOS security features announced in 2012. Signal didn't wait for NIST when it rolled out the first version of its cryptographic protocol, and the second version, and the third version, and the fourth. Google didn't wait for NIST when it started its post-quantum experiment in 2016. So this general fear of cryptography doesn't explain why Google suddenly turned the experiment off.
Cryptographic expertise doesn't magically eliminate the risk of something going wrong. An expert switching from RSA-2048 to some post-quantum proposal could be destroying all security. Expertise isn't omniscience; maybe the post-quantum proposal is vulnerable to attack algorithms that the expert isn't familiar with or that simply haven't been developed yet. (This doesn't mean that large-scale attackers have missed the attacks!)
NIST's Post-Quantum Cryptography Standardization Project set a 2017 deadline and received 69 complete submissions. Almost all of those submissions have less security against attacks known today than against attacks considered in the submission documents. About half of the submissions have been shown to not reach their claimed security levels. Sometimes a submission has been shown to have such a low security level as to be rapidly broken by a Python script running on a laptop.
The difficulty of evaluating cryptography means that, unfortunately, the area attracts fraudsters trying to fool buyers into believing that their solutions are in a fantasy world that's magically guaranteed to be secure. Sometimes the buyers hear about new attacks, and the fraudsters make up ad-hoc excuses for why each new attack should be ignored. But Google isn't living in this fantasy world. That's why Google's experiment used double encryption (to be more precise, a double KEM), securing everything with the New Hope post-quantum system and with the X25519 elliptic-curve system:
By adding a post-quantum algorithm on top of the existing one, we are able to experiment without affecting user security. The post-quantum algorithm might turn out to be breakable even with today's computers, in which case the elliptic-curve algorithm will still provide the best security that today’s technology can offer. Alternatively, if the post-quantum algorithm turns out to be secure then it'll protect the connection even against a future, quantum computer.
This matches the mainstream view of how post-quantum cryptography should be and will be deployed for the foreseeable future. Maybe someday we'll see X25519 being broken by quantum computers so efficiently that we might as well turn it off, and hopefully by then we'll be using post-quantum cryptosystems mature enough to justify confidence, but today continuing to encrypt everything with X25519 is an obvious win.
(When I say "mainstream", I'm excluding NSA, an organization that secretly asked whether a "public encryption standard" could be made "weak enough to still permit an attack of some nature using very sophisticated (and expensive) techniques"; that has a massive budget for undermining cryptographic standards; and that today is trying to convince everyone to jump into lattices and immediately turn off ECC.)
To summarize: The new post-quantum system could be much cheaper to break than ECC. Was Google's experiment switching from ECC to that system? Was Google dealing with the new security risk by turning off the experiment and switching back to ECC? No. Google was adding the post-quantum system on top of ECC, exactly to make sure that the combination wasn't losing security compared to just ECC. But then why was the experiment terminated?
In its July 2016 announcement of the experiment, Google said that it didn't want to set a standard so it would hopefully be upgrading to something better within two years. After just 20% of that time, in November 2016, Google said that it didn't want to set a standard so it was immediately turning the experiment off. Wait, what?
Let's look at Google's words. July 2016, part of the same announcement quoted above:
We explicitly do not wish to make our selected post-quantum algorithm a de-facto standard. To this end we plan to discontinue this experiment within two years, hopefully by replacing it with something better.
But then November 2016:
We do not want to promote CECPQ1 as a de-facto standard and so a future Chrome update will disable CECPQ1 support. It's likely that TLS will want a post-quantum key-agreement in the future but a more multilateral approach is preferable for something intended to be more than an experiment.
Google's July 2016 position makes perfect sense: Google was clearly saying that it didn't want to promote CECPQ1 as a de-facto standard, and that it was planning to upgrade from CECPQ1 to something else. Obviously anyone else considering CECPQ1 experiments would have to be agile enough to upgrade along with Google. How did this mutate into Google's November 2016 position, turning off an algorithm that could protect users against the quantum apocalypse?
If Google had said from the beginning that it was doing a short experiment to collect data and would turn everything off three months later, then, okay, that would have been perfectly believable. Quantum computers, like climate change, are beyond the planning horizons of most companies. Simply getting a company interested enough in post-quantum cryptography to run a brief experiment would have been a success.
But Google took the trouble to write a blog post in July 2016 explaining the quantum threat; saying this was "something that we should be thinking about today"; saying how "excited" it was to begin preparing; explaining the CECPQ1 experiment; and expressing its hope that it would discontinue the experiment "by replacing it with something better". This is definitely not the same as what Google suddenly did a few months later, namely replacing the experiment with nothing. What's going on here?
Reportedly, after announcing its experiment, Google was contacted by Jintai Ding, who informed Google that he had a patent covering New Hope and asked them for money.
If that's in fact what happened, then suddenly it makes sense that Google's enthusiasm for running the experiment would have rapidly disappeared. Imagine the effect of email saying "A patent holder is asking us for money because of your CECPQ1 experiment" from one of Google's patent lawyers to the managers at Google in charge of TLS.
Actually, because intentional patent infringement is subjected to triple damages under patent law, the lawyers at big companies try to avoid sending email that could end up making any subsequent infringement sound intentional. So instead imagine the TLS managers receiving requests from the Google higher-ups to fill out painful paperwork
These requests would carefully avoid saying anything about patents, but the impact would be the same.
Ding does have a patent that threatens New Hope: U.S. patent 9246675, expiring 2033. The statement "A provisional patent application was filed" already appeared in the first version of Ding's key-exchange paper, long before New Hope existed. More than a year later, the fourth version of the paper, labeled as a conference submission, removed that statement, but Ding highlights patents on the first page of his publication list.
The knowledge that Ding had a patent threatening New Hope—along with the idea that this is what stopped Google's experiment—spread rapidly among cryptographers as 2016 drew to a close. Suddenly it makes sense that everyone, not just Google, was skittish about rolling out post-quantum cryptography.
Doesn't the cryptographic community prioritize unpatented cryptosystems? Why would anyone other than Ding have been putting effort into developing a cryptosystem threatened by Ding's patent? Why were the New Hope developers starting from that cryptosystem in the first place? If they had some reason to do this, why wasn't their paper prominently warning people regarding the patent threat?
Let's go back to the videotape. The New Hope paper from Alkim–Ducas–Pöppelmann–Schwabe appeared online in November 2015, saying that it was an improvement over a previous example of "Peikert's ring-learning-with-errors (Ring-LWE) based key-exchange protocol":
Earlier in 2015, Bos, Costello, Naehrig, and Stebila (IEEE Security & Privacy 2015) proposed an instantiation of Peikert's ring-learning-with-errors (Ring-LWE) based key-exchange protocol (PQCrypto 2014), together with an implementation integrated into OpenSSL, with the affirmed goal of providing post-quantum security for TLS. In this work we revisit their instantiation and stand-alone implementation.
Peikert's paper, in turn, appeared online in February 2014, saying that it was an improvement over previous work from Lyubashevsky–Peikert–Regev ("LPR"):
One of our main technical innovations (which may be of independent interest) is a simple, low-bandwidth reconciliation technique that allows two parties who "approximately agree" on a secret value to reach exact agreement, a setting common to essentially all lattice-based encryption schemes. Our technique reduces the ciphertext length of prior (already compact) encryption schemes nearly twofold, at essentially no cost. ...
Our first technical contribution is a new ring-LWE-based KEM that has better bandwidth (i.e., ciphertext length) than prior compact encryption/KEM schemes [LPR10, LPR13] by nearly a factor of two, at essentially no cost in security or other efficiency measures. The improvement comes from our new, simple "reconciliation" technique that allows the sender and receiver to (noninteractively) reach exact agreement from their approximate or "noisy" agreement on a ring element. (See Section 3 for details.) Compared to the encryption schemes of [LPR10, LPR13], this technique allows us to replace one of the two ring elements modulo q = poly(n) in the ciphertext with a binary string of the same dimension n, thus nearly halving the ciphertext length. (See Section 4 for details.) We remark that approximate agreement is common to essentially all lattice-based encryption and key-agreement protocols, and our reconciliation technique is general enough to apply to all of them. ...
As compared with the previous most efficient ring-LWE cryptosystems and KEMs, the new reconciliation mechanism reduces the ciphertext length by nearly a factor of two, because it replaces one of the ciphertext's two Rq elements with an R2 element. So the ciphertext length is reduced from 2n log q bits to n(1+log q) bits, where n is both the dimension of R and the length of the agreed-upon key.
The reason there are two different LPR citations here is that "LPR10" used power-of-2 cyclotomics (which is also what New Hope did) while "LPR13" considered more general cyclotomics. Either way, 2014 Peikert claims credit for
What 2014 Peikert didn't say is that the same space reduction had already appeared in a paper from Ding in December 2012.
Let's look at the details. The LPR cryptosystem is often described as being like the Diffie–Hellman cryptosystem but adding noise; let's use notation that's as similar as possible to Diffie–Hellman notation so that we can easily see what's the same and what's different.
In elliptic-curve Diffie–Hellman, Alice's public key has the form A = aG, where a is Alice's secret key and G is a standard generator that everybody uses. Bob's public key has the form B = bG, where b is Bob's secret key and G is the same standard generator. Alice computes aB = abG. Bob computes bA = baG, which is the same as abG since a and b commute. At this point Alice and Bob both know a shared secret, namely abG; hopefully the attacker can't figure out this secret.
Other users can broadcast their own public keys. Each pair of users automatically shares a secret the same way that Alice and Bob do, with no interaction beyond the public-key broadcasts. This is what's called a "non-interactive key-exchange system".
Let's focus on the following "key-encapsulation mechanism". There's just one public key, Alice's A = aG. Bob then sends a "ciphertext" B = bG, which "encapsulates" the "session key" abG, which Alice and Bob each compute. There's nothing new happening here: this is an example of Diffie–Hellman, with Bob's public key relabeled as "ciphertext".
Nowadays people typically use, e.g., a SHA-256 hash of this secret abG as an AES-256-GCM key to authenticate and encrypt messages. But let's rewind to the 1980s, specifically to the "ElGamal public-key-encryption system", which works as follows. There's again just one public key, Alice's A = aG. Bob sends a two-part ciphertext, where the first part is B = bG, and the second part is C = M+bA for some secret message M. Alice computes aB as before, and subtracts aB from C to obtain M.
The LPR cryptosystem looks slightly different: Alice's public key has the form A = aG+e. Notice the extra term e, a secret "error" that Alice deliberately introduces into A. Bob sends a two-part ciphertext, where the first part is B = bG+d and the second part is C = M+bA+c. Alice computes C−aB = (M+b(aG+e)+c)−a(bG+d) = M+(be+c−ad).
In the elliptic-curve context, reconstructing M would be hopeless at this point. The LPR cryptosystem addresses this as follows. Switch from scalar multiplication on an elliptic curve to multiplication in, for example, the ring (Z/12289)[x]/(x1024+1); this is the ring of polynomials in one variable x modulo x1024+1 with integer coefficients modulo 12289. Require a,b,c,d,e to be small ring elements, meaning small linear combinations of 1,x,x2,...,x1023. Require M to take each coefficient from a set of integers that aren't close to each other: concretely, let's say M is a linear combination of 1,x,x2,...,x1023 where each coefficient is either 0 or 6144. The point of all this is that be+c−ad isn't very large, so Alice can recover M by rounding each coefficient of C−aB = M+(be+c−ad) to either 0 or 6144.
Filling in all the details here requires saying quantitatively what "small" means, and making sure that "isn't very large" is between −3071 and 3071 in each coefficient. Then a 0 coefficient in M will end up between −3071 and 3071, rounding back to 0, and a 6144 coefficient in M will end up between 6144−3071 and 6144+3071, rounding back to 6144. As a concrete example, let's say that c is between −1536 and 1536 in each coefficient; and let's say that a,b,d,e each have coefficients −1 or 0 or 1, which makes it seem overwhelmingly likely that be−ad is between −1535 and 1535 in each coefficient. (The consequences of occasional decryption failures are outside the scope of this blog post.)
It's easy to match this example up to the LPR cryptosystem, the cryptosystem presented on page 4 of the 2012 version of the LPR paper. Here's a translation table:
It's also easy to match this example up to the 2014 Peikert description of LPR as sending "two ring elements modulo q = poly(n) in the ciphertext": q is 12289; n is 1024; the ring is (Z/12289)[x]/(x1024+1); the ciphertext has the two ring elements B and C. Concretely, a conventional encoding of an element of this ring uses 1739 bytes, and then an LPR ciphertext for this ring uses 3478 bytes.
Here's a series of three simple cryptosystem modifications. This series starts with cryptosystem 0, the LPR system described above, and ends with cryptosystem 3, the compressed LPR system from 2012 Ding.
Cryptosystem 1: Instead of generating c independently of the other secrets, let's obtain C = M+bA+c by rounding M+bA to a limited set. Concretely, let's round each coefficient of M+bA to either 0, 3072, 3072·2, or 3072·3. This keeps the c range mentioned above, adding something between −1536 and 1536 into each coefficient, but the deterministic choice squeezes each coefficient of C into just 2 bits.
Cryptosystem 2: Instead of generating M independently, let's choose M as a deterministic function of bA, arranging for each coefficient of M+bA to be between −1536 and 3072+1536. This is compatible with taking each coefficient of M as either 0 or 6144. Then we can round each coefficient of M+bA to produce 0 or 3072, so each coefficient of C uses just 1 bit.
Bob's ciphertext now has B, a full ring element (1739 bytes); and C, which has been squeezed into 1024 bits (128 bytes). This is 1867 bytes in total, a big improvement over the original 3478 bytes.
Cryptosystem 3: Let's do some superficial relabeling. Starting from the equations −2A = −a(2G)−2e, −2B = −b(2G)−2d, −2C = −2M+b(−2A)−2c, and (−2C)−a(−2B) = −2M+(−2be−2c+2ad), let's relabel −2A as A (the new public key), −2B as B (the new ciphertext part 1), −2C as C (the new ciphertext part 2), −2G as G, −2M as M, −c as c, −d as d, and −e as e to obtain the equations A = aG+2e, B = bG+2d, C = M+bA+2c, and C−aB = M+2(be+c−ad). One can also reformulate the rounding steps in terms of these new labels.
The new labels make the computations sound different: the errors c,d,e are now being doubled, M now has coefficients 0 or 1 (instead of 0 or 6144) to force each coefficient of M+bA to be even, C has each coefficient chosen as 0 or −6144 to make C−bA small, and each rounding step sounds different. But multiplication by −2 is invertible (since q is odd), so cryptosystems 2 and 3 are equivalent. (If q is even then cryptosystem 3 is a security disaster and this equivalence breaks, but let's focus on odd q, as in New Hope.)
It's easy to see how cryptosystem 3 matches the cryptosystem on page 11 of 2012 Ding, specifically with Ding's small prime number "t" chosen to be 2 (which is a choice of "t" that Ding's paper mentions as an example, and in any case is one of the most obvious numbers to try if someone is asking for a small prime number). Translation table this time:
Does this mean that 2012 Ding achieved the best possible space efficiency for this family of cryptosystems? No. For example, one can further compress C by sending just 256 coefficients (or sums of coefficients, as in New Hope) to transmit 256 bits of M instead of 1024; 256 bits have enough entropy for a high-security session key. As another example, regarding parameter choices, 2012 Ding suggested taking q around n3; this makes certain types of analysis easy but is suboptimal.
But 2012 Ding did reduce the LPR ciphertext size "nearly twofold", specifically replacing "one of the two ring elements" with "a binary string of the same dimension n", in the words of 2014 Peikert. The problem is that this isn't how 2014 Peikert was describing 2012 Ding; this was 2014 Peikert claiming this space reduction as something new, the result of an "innovation" in 2014 Peikert.
Schoolchildren are taught that if they copy text then they have to use quotation marks around that text, and that copying text without quotation marks is plagiarism. But this is just one form of plagiarism. In the words of the Office of Research Integrity at the U.S. Department of Health and Human Services, "appropriating someone else's idea (e.g., an explanation, a theory, a conclusion, a hypothesis, a metaphor) in whole or in part, or with superficial modifications without giving credit to its originator" is "plagiarism of ideas". In the words of the Ethical Guidelines of the American Mathematical Society:
The knowing presentation of another person's mathematical discovery as one's own constitutes plagiarism and is a serious violation of professional ethics. Plagiarism may occur for any type of work, whether written or oral and whether published or not.
The correct attribution of mathematical results is essential, both because it encourages creativity, by benefiting the creator whose career may depend on the recognition of the work and because it informs the community of when, where, and sometimes how original ideas entered into the chain of mathematical thought. To that end, mathematicians have certain responsibilities, which include the following:A claim of independence may not be based on ignorance of widely disseminated results.
- To endeavor to be knowledgeable in their field, especially about work related to their research;
- To give appropriate credit, even to unpublished materials and announced results (because the knowledge that something is true or false is valuable, however it is obtained);
- To publish full details of results that are announced without unreasonable delay, because claiming a result in advance of its having been achieved with reasonable certainty injures the community by restraining those working toward the same goal;
- To use no language that suppresses or improperly detracts from the work of others;
- To correct in a timely way or to withdraw work that is erroneous.
Often two people do independently come up with the same idea. This fact provides cover for people who are, in fact, plagiarists: they can claim that they came up with the idea independently. But the scientific rule is that credit is given to the first publication of an idea. There are occasional exceptions to this rule, giving joint credit to the first and second publication when the publications are very close in time and the second publication plausibly claims to have found the idea before the first publication appeared; but 2014 Peikert doesn't claim to have come up with the idea before 2012 Ding appeared (never mind the plausibility question regarding such a claim), and 2014 Peikert isn't nearly close enough in time to 2012 Ding to try invoking this exception in the first place.
Let's charitably assume that there was no information flow to Peikert from Ding and from other people discussing Ding's work, people who had seen Ding's paper or who had heard the talks that Ding had already given on this in June 2012 and November 2012. Let's also charitably assume that Peikert tried to "be knowledgeable in their field, especially about work related to their research" but failed: he wrote and posted a 2014 paper on key exchange based on Ring-LWE while managing to completely miss a 2012 paper "A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem" (pointing specifically to "ring LWE" at the end of the abstract) that had appeared on the same cryptographic preprint server where Peikert posts his own papers. There were more than 700 papers on that preprint server in 2012; imagine how time-consuming it would be to read two new paper abstracts every day!
So far this is simply a story of shoddy scholarship. What turns this into a clear-cut case of plagiarism is that, after learning about Ding's paper, Peikert didn't give appropriate credit to that paper.
Is it possible that Peikert didn't learn about Ding's paper? No. The bibliography of the July 2014 revision of Peikert's paper includes "[DXL14] J. Ding, X. Xie, and X. Lin. A simple provably secure key exchange scheme based on the learning with errors problem. Cryptology ePrint Archive, Report 2012/688, 2014"; that's a 2014 revision of Ding's paper.
Is it possible that Peikert was merely citing "DXL14" for some other reason, without realizing that it was saving space? No. Page 9 of Peikert's revision admits that "DXL14" was saving space:
We remark that a work of Ding et al. [DXL14] proposes a different reconciliation method for lower-bandwidth "approximate agreement," in the context of a key exchange against a passive adversary.
Starting from this knowledge, did Peikert issue an appropriate erratum, prominently stating "A previous version of this paper claimed credit for low-bandwidth reconciliation to reduce the LPR ciphertext length nearly twofold, but there is important prior work from Ding in 2012 already achieving this"? No. On the contrary, the abstract of Peikert's revision continues to claim credit for a "technical innovation" that "reduces the ciphertext length of prior (already compact) encryption schemes nearly twofold":
One of our main technical innovations (which may be of independent interest) is a simple, low-bandwidth reconciliation technique that allows two parties who "approximately agree" on a secret value to reach exact agreement, a setting common to essentially all lattice-based encryption schemes. Our technique reduces the ciphertext length of prior (already compact) encryption schemes nearly twofold, at essentially no cost.
Everything that 2014 Peikert says it's accomplishing here is something that 2012 Ding had already done!
A naive model of the patent system says that the public knows what's patented and, if unwilling to pay for it, can simply avoid using it. Patents become much more dangerous when the people making usage decisions don't know what's patented. Think about how people in industry feel when they see a company stepping on the intellectual-property equivalent of a land mine: "If the New Hope developers fell into the trap of optimizing a post-quantum system threatened by a patent, and Google fell into the trap of deploying a post-quantum system threatened by a patent, then how are we supposed to avoid the same trap?" This fear extends beyond the scope of the problems that are known:
So it takes years to convince industry to take tentative further steps into the minefield.
In principle, patents are public, and patent applications are published within 18 months of filing (assuming publication hasn't been slowed down by, e.g., an NSA secrecy order; yes, U.S. patent law allows NSA to issue secrecy orders). In reality, the ten millionth patent in the U.S. was issued in 2018, there are important complications and uncertainties in understanding the scope of each patent, and the U.S. is just one of many countries. Trying to track what's patented is a massive information-management problem.
Of course, patents.google.com allows full-text patent searches, but which words are you going to search for? "Cryptography" gives 106778 results. That's obviously missing a lot: "cryptosystem" gives 135304 results, and what happens if a patent says "encryption system" or "communicating secretly" or "protecting data"? Meanwhile the French word "cryptographique" gives 14172 results, almost never saying "cryptography" or "cryptosystem".
Let's say you manage to identify all the cryptographic patents. Within those, you're trying to find patents specifically on cryptosystems using polynomial multiplication. What happens if the polynomial multiplication doesn't say "polynomial" or "multiplication"? Maybe it says "convolution" of "signals". Maybe there's a mathematical description of two randomly named variables R,S in k[t]/(tn+1), and the multiplication is expressed by concatenation of the variable names. Maybe there are structured matrices instead of polynomials. Sure, you could get lucky on any particular search, and I frequently try full-text patent searches, but I don't expect these searches to be anywhere near comprehensive.
Searching for patents on X becomes much more tractable when you know who introduced X. Patents are required by law to list their "inventors", and patents.google.com allows searches by "inventor". This narrows the original pool of more than ten million patents down to a vastly smaller list of patents from a particular source. This procedure by itself isn't perfectly reliable (it misses "submarine" cases where a patent holder abandons scientific credit to try to hide a patent), but it's tremendously valuable.
Fundamentally, the question of who introduced X is the same information that scientists publishing papers on X are ethically obliged to report, but now the stakes are much higher. There isn't an exact match between the scope of a patent monopoly and the credit that the patent holder is scientifically entitled to receive, but there's nevertheless an important overlap between the process of assigning scientific credit and the process of finding relevant patents. Plagiarism damages one of the most important processes for managing patent risks.
Imagine yourself in the role of the attacker in this story. You're desperate for credit, so desperate that you've plagiarized someone else's work. Obviously you want to limit the number of people who realize that you're a plagiarist. People who realize this won't give you credit. You might even get into trouble: you've been violating basic ethics rules that you can't plausibly claim to be unaware of. So, okay, how can you stop people from seeing what's going on?
If you had copied text word by word then anyone comparing the original text to "your" text would immediately see the copying. The first important point to realize is that plagiarism of ideas isn't so easy to see. Sure, you can see that the result you're claiming credit for was already achieved by the original source, but think about how many words you've been reading and understanding to see this. How many people in the world are starting with the necessary background knowledge? Out of those, how many will take the time to read and understand for themselves? Why would someone want to spend this time in the first place?
This is the 21st century. People are busy. People are flooded with information, often contradictory information, and don't have time to dig into every contradiction. You can exploit this!
Let's look at your basic defense strategies. For each strategy, I'll explain the point of the strategy first, and then give an illustrative example of what is, as far as I can tell, the strategy being put into action.
Strategy 1: deflection. Preemptively cite the original source and say something else about it. The attitude you want to project here is "I'm such a careful scholar that I'm citing this faraway work to explain its tiny connections to my paper". Don't go out of your way to claim that the original source doesn't do what you trumpeted as your own contribution; instead focus the reader on some other aspect of the original source, preferably something that makes the original source sound as useless as possible.
Example of strategy 1 in action. Above I quoted the July 2014 version of Peikert's paper claiming credit for a "technical innovation" that "reduces the ciphertext length of prior (already compact) encryption schemes nearly twofold", and then finally getting around to citing Ding:
We remark that a work of Ding et al. [DXL14] proposes a different reconciliation method for lower-bandwidth "approximate agreement," in the context of a key exchange against a passive adversary.
The text goes on to complain about non-uniformity of the "DXL14" output. Structurally, this sounds like what one would say about a faraway reference: there's some "DXL14" paper presenting a different space-saving idea in a different context, something not even worth mentioning before page 9, something that would need all sorts of changes and improvements to turn into this paper's innovation. The reader assumes that all of this is consistent with the claim of novelty for reducing the LPR ciphertext length nearly twofold.
Strategy 2: ad-hominem attacks. What happens if the reader is curious what's in Ding's paper? The reader might see that Ding already reduced the LPR ciphertext length nearly twofold! As for your deflection efforts, the reader might notice how little the non-uniformity matters given the standard practice of hashing session keys, might notice that generic conversions already upgrade passive security to active security, and, most fundamentally, might notice that whatever differences there are between the techniques can't justify your failure to prominently credit Ding for the overlap between the techniques.
So discourage the reader from reading Ding's paper. The technical side of this, making Ding's paper sound as useless as possible, was already covered above. But there's also an emotional side of this, priming the reader to view Ding as the enemy, to view Ding as the scientific equivalent of a manipulative talk-show host from that other political party, an evil demagogue that only a fool would listen to. (You know which political party I'm talking about, right?)
Example of strategy 2 in action. I've heard that Ding patents other people's ideas and thus deserves whatever punishment he gets. I've heard that Ding maliciously misrepresents history, for example refusing to credit LPR. I've heard that Ding violated scientific naming conventions when he submitted the self-named "Ding Key Exchange" to NISTPQC in 2017. I've heard that Ding portrays himself as a leading figure in lattice-based cryptography, even though the citation counts show that he's less important than Peikert. Et cetera. Am I looking at a paper from someone like that? Yuck!
As you'd expect from the worst forms of small-audience politics, most of this is kept behind the scenes where Ding can't see it and can't defend himself. But this sort of thing has a real impact. I'm sure these attacks have added to the difference in citation counts between 2014 Peikert and 2012 Ding. This difference helps bolster the idea that 2014 Peikert is more important than 2012 Ding, which in turn encourages authors who haven't investigated (i.e., most authors) to cite 2014 Peikert. How can 2014 Peikert's highlighted "innovation" be plagiarism, a ripoff of 2012 Ding, if so many scientists have agreed to cite 2014 Peikert?
Strategy 3: obviousness weaseling. Maybe the deflection and the ad-hominem attacks won't be sufficient to deter all of the potential readers of the original source. There's a third strategy you can and should follow: claiming that the original source was saying things that were already obvious given the prior art. By "prior art" I mean things predating the original source.
You might think there's a glaring contradiction between (1) claiming X as an "innovation" in your own paper and (2) claiming that X in the original source was obvious from the prior art. Stop worrying so much! Here's how this strategy works:
Sure, a reader who goes carefully through everything will see the game you're playing, but the whole point here is to give the reader an easy excuse for not going carefully through everything. Why should the reader bother reading the original source when the original source is doing so little compared to the prior art?
Example of strategy 3 in action. Let's look at the gap between two portrayals of one paper. This paper is 2009 Peikert, by which I mean the version dated September 2009 of Peikert's paper "Public-key cryptosystems from the worst-case shortest vector problem". One portrayal of this paper is in 2014 Peikert, emphasizing how limited 2009 Peikert is, so as to highlight 2014 Peikert's contributions. The other portrayal is in a 2021 Peikert posting, suppressing the same limitations of 2009 Peikert, so as to downplay 2012 Ding's contributions. Of course, the third edge of the triangle, comparing 2014 Peikert to 2012 Ding, is omitted.
Here's July 2014 Peikert emphasizing how limited 2009 Peikert is:
We mention that going back at least to the public-key cryptosystem of [Pei09], it has been known that one can improve ciphertext length by simply "rounding," i.e., dropping less-significant bits. However, the resulting modulus must still remain larger than the norm of the secret key—in particular, polynomial in n—whereas our technique is able to "round" (in a certain way) all the way to a modulus of two.
Indeed, Section 4.2 of 2009 Peikert uses a post-rounding modulus chosen to be at least "4(m+1)", with m being above n log2 q. (For example, if n is 1024 and q is 12289, then m is above 13·1024, so the post-rounding modulus would be above 13·4·1024 and thus even larger than q, going the wrong direction.) This lower bound on the modulus is used directly in the analysis of whether the cryptosystem can decrypt. The advertisement at this point in 2009 Peikert says, basically, that certain cryptosystems have a superpolynomial LWE modulus, and the 2009 Peikert rounding switches to a polynomial LWE modulus, saving ciphertext size:
When using a large value of q (e.g., q = 2O(n)), however, the efficiency of the prior schemes is suboptimal, because the plaintext-to-ciphertext expansion factor (even in the amortized schemes) is at least lg q. Fortunately, it is possible to improve their efficiency (without sacrificing correctness) by discretizing the LWE distribution more 'coarsely' using a relatively small modulus q′ = poly(n).
A reader who sees 2009 Peikert and then LPR has no reason to think that replacing LWE with Ring-LWE in the 2009 Peikert rounding would give an improvement in the LPR cryptosystem: the LPR cryptosystem is starting with a polynomial Ring-LWE modulus in the first place.
Given this limitation of 2009 Peikert, it makes sense that the full version of the LPR paper in April 2012, a paper highlighting efficiency, doesn't say anything about using rounding to compress LPR ciphertexts. It makes sense that 2014 Peikert dismisses 2009 Peikert as requiring a large post-rounding modulus. Everything here is consistent with 2014 Peikert saying it improves "the ciphertext length by nearly a factor of two" compared to "the previous most efficient ring-LWE cryptosystems and KEMs": specifically, saying that "the ciphertext length is reduced from 2n log q bits to n(1+log q) bits" (log here obviously being log2).
Except, oops, 2012 Ding already compressed LPR ciphertexts from 2n log q bits to n(1+log q) bits. How do you stop the reader from looking at 2012 Ding? The strategy here is to make the reader believe that 2012 Ding wasn't adding anything of interest beyond 2009 Peikert!
Here's the treatment of 2009 Peikert in a 2021 Peikert posting trying to downplay Ding's contribution (and dodging discussion of 2014 Peikert). 2021 Peikert refers to modern LPR-style proposals such as Kyber and claims that "it's implausible that the proposals' round-low-bits compression could be covered by the cited patent", since "the technique was already well established by abundant prior art to the 2012 patent application" and "the patent does not claim or even describe the method, probably because it needs to avoid that very prior art".
Which prior art, precisely? Here 2021 Peikert cites 2009 Peikert, describes 2009 Peikert as using "rounding to compress the ciphertext", and then leaps to the claim that "rounding works just as well" for LPR etc. Just as well as, um, using modulus at least 4(m+1)? The big modulus in 2009 Peikert is highlighted (in 2014 Peikert) when the goal is to say how innovative 2014 Peikert is, but is suppressed (in 2021 Peikert) when the goal is to say how little 2012 Ding contributed. Very few readers will look closely enough to notice the deception.
2021 Peikert continues by bombarding the reader with further references, one on the use of rounding in LWR and two on the use of rounding in FHE. Of course, 2021 Peikert doesn't admit that these references also fail to achieve Ding's nearly twofold compression of LPR ciphertexts.
In principle, to see that 2014 Peikert plagiarized 2012 Ding, the reader doesn't have to read any of the older work. The reader simply has to (1) read 2014 Peikert to see what 2014 Peikert claims as new and (2) read 2012 Ding to see that 2012 Ding already achieved that result. But the point of the 2021 Peikert bombardment is to give the reader the impression that whatever Ding did was already obvious from the prior art. This impression, in turn, gives the reader an excuse to not read Ding's paper in the first place.
It's useful to think through what would have happened if, back in 2014, Peikert had given proper credit to Ding. Instead of starting from "Peikert's ring-learning-with-errors (Ring-LWE) based key-exchange protocol", the New Hope authors would have understood that they were starting from Ding's key-exchange protocol. This doesn't guarantee that they would have noticed Ding's patent (the BCNS paper cited Ding without mentioning patents), but it would have given them a much better chance of noticing it. Let's consider specifically the scenario of them being aware of the problem.
Presumably the New Hope authors would have tried to find a way around the patent. The obvious path forward here is to optimize NTRU instead of LPR. This is essentially the path taken by Hülsing–Rijneveld–Schanck–Schwabe in July 2017. NTRU was still patented by the time New Hope appeared in November 2015, but NTRU's patent expiration, August 2017, wasn't that far away. I was already putting work into NTRU in anticipation of the work becoming usable starting in 2017; an initial NTRU Prime design was already online in February 2014, and the NTRU Prime paper appeared in May 2016.
(There's tremendous overlap between optimizing NTRU and optimizing LPR, and known attacks end up being practically identical for the same size constraints, as illustrated by how close Streamlined NTRU Prime and NTRU LPRime are in Core-SVP levels, ciphertext sizes, and key sizes. Renaming NTRU and LPR as "Quotient NTRU" and "Product NTRU" respectively does a better job of recognizing the similarities between the systems. Regarding the risks of unknown attacks, the LPR marketing department hypes one attack avenue that exists in NTRU and not in LPR, while failing to admit that there are three attack avenues that exist in LPR and not in NTRU.)
A more dangerous path is to stay with LPR but try to find a way around Ding's patent. This is essentially the path taken by Alkim–Ducas–Pöppelmann–Schwabe in December 2016, introducing "New Hope without reconciliation" and claiming that it "avoids the error-reconciliation mechanism originally proposed by Ding".
Why is it dangerous for scientists to look at a patent and skirt the edges of the patent? One reason is that the edges are determined by rules followed by patent courts, rules that the scientists generally don't know. How many scientists know what a Markman hearing is? How many scientists have spent time studying the doctrine of equivalents? It's horrifying to see that a scientific-sounding PDF making claims about the validity and applicability of a patent was written by people who say "court procedure was not the point of our writeup (since we don't pretend to know it)". If you saw a PDF making claims about, say, IND-CCA2 security, wouldn't you expect the authors to know the definition of IND-CCA2 security?
I've looked closely at the claimed dividing lines between Ding's work and subsequent variants of Ding's work. As far as I can tell, these dividing lines don't even meet the basic standards of clarity enforced by court procedures, never mind the question of whether they can escape the doctrine of equivalents in the U.S., never mind the fact that we want cryptography usable worldwide and also need to investigate the impact of, e.g., the European version of Ding's patent.
Scientifically, New Hope owes an intellectual debt to Ding for showing how to compress LPR ciphertexts. Switching to "New Hope without reconciliation" doesn't evade this debt. Switching to modules, as in Kyber, also doesn't evade this debt; it's not as if Kyber eliminated the compression! The fact that there are differences in the details doesn't eliminate the core overlap of ideas, and it's this overlap that requires crediting Ding. It's certainly possible that poor patent drafting narrowed the scope of Ding's legal monopoly below Ding's scientific contribution, but the doctrine of equivalents and other court procedures tilt the system towards patent holders, and people who aren't familiar with these procedures simply aren't competent to evaluate patent threats.
Another reason that coming close to a patent is dangerous is that if you're in an area that has a new patent then you shouldn't be surprised to bump into further patents. Sure, there could be a land mine anywhere, but the reality is that some areas are more mature than others, making those areas generally less attractive to people looking for things to patent. Patents naturally tend to cluster in less mature areas.
Today there's broad awareness of U.S. patent 9094189, a patent on the LPR cryptosystem, filed before LPR published the cryptosystem. This broad awareness didn't exist in 2016, but someone seeing Ding's patent shouldn't be surprised to hear that there's a patent on LPR; shouldn't be surprised to hear about Chinese patent 107566121, which covers something that sounds very similar to "New Hope without reconciliation" and was filed in November 2016; shouldn't be surprised to hear about the local land-mine-planting company; and so on.
(Should the LPR cryptosystem be called the LPR cryptosystem? The first publications, as far as I know, were LPR talks in April and May 2010. But the patent holders also gave a talk on the cryptosystem in May 2010, with slides online a few days later. So this could be one of the exceptional cases where credit should be given to both sources. I'll return to this question in a subsequent blog post. Anyway, under patent law, what counts is the filing date of the patent application.)
Would the New Hope authors have taken this dangerous path if they had known about Ding's patent earlier, before investing any work in New Hope? Hard to guess. Maybe "New Hope without reconciliation" would have been the first "New Hope", with the paper pointing to Ding's patent and claiming to avoid it. Or maybe the "New Hope" label would have been used for an optimized NTRU instead, with the paper pointing to Ding's patent and commenting on NTRU having the advantage of being patent-free starting 2017.
Either way, Google and other potential users would have had a much higher chance of realizing from the outset that there were new patents to worry about, not just the old soon-to-expire NTRU patent. Seeing a problem in advance can be a reason to hesitate, but is much less traumatic than getting burned as a result of not seeing the problem. My best guess is that industry would have started years earlier on NTRU deployment, and would have ramped up to broad deployment much faster.
There could still be big problems lurking in the shadows. Original NTRU is no longer patented, but, as noted above, modern versions of NTRU are different from original NTRU, so there could be patent threats that we've missed. Furthermore, the state of the art in lattice attacks is unstable, with many inadequately explored attack avenues, as illustrated by S-unit attacks breaking one claimed "barrier" after another. But I hope that what's being rolled out now is (1) patent-free and (2) at least strong enough to meaningfully limit the number of users attacked by future quantum computers. The risk of something going horribly wrong with NTRU doesn't justify our failure as a community to start encrypting as much data as we could with NTRU in 2017.
Note added 2024.07.21: NSA's Art Drisko has paid $20.