In Defense of Money Privacy

TL;DR. With the increasing popularity of privacy-preserving cryptocurrencies, opponents are redoubling their effort to curtail permissionless money, citing money laundering concerns. However, money laundering is a red herring: it is an ethically vacuous notion whose net effect is to keep entrenched powers entrenched.

Introduction

One of the most common critiques of private money relates to its capability to launder money. According to this line of reasoning, privacy in the realm of money is bad because money laundering is bad. Serious ongoing efforts to eliminate private moneys such as cash and private cryptocurrencies are motivated by this belief.

However, humans have been using private means of payment since the dawn of civilization, namely in the form of untraceable coins and later bank notes. The enduring use and very long existence of these inherently private moneys suggests more than just convenience; it suggests a fundamental need for privacy that comparatively recent trends seem to be overlooking.

The rapid digitization of everything threatens to erase privacy in all walks of life. This erasure is partly organic: companies can serve their customers better the more they know about them. But it is also to a large degree driven by the state, for better or for worse. The on-going erasure of privacy is especially true in the case of money. However, this trend of digitization is incapable of erasing a fundamental human need for anonymous transactions.

Today we have the technologies that enable digitization of money while preserving users’ privacy: privacy-preserving cryptocurrencies. This note argues that these technologies should be celebrated rather than fought. Legislative efforts to curtail their use are misguided and run counter to essential civil liberties.

Illegal versus Immoral

It is important to separate the legal question from the ethical question in regards to private money. The legal question has to do with the laws that are enforced by the state, how those laws come about, how they are interpreted, and the mechanisms that enforce them. The ethical question exists purely in the context of dialectic, and is rather more subjective in the sense that there is no final arbiter of truth. People can and do disagree about moral questions.

An article in defense of private money (and indeed, as do the accusations and allegations it defends against) fall squarely in the category of moral questions. One cannot derive from the laws that are on the books a proposition about which laws ought to be on the books. Nor is it possible to derive a moral imperative from a ban.

The distinction may seem obvious when stated in the abstract, but all too often a debate regarding private money is framed in a way that presupposes the moral framework of the state. This fallacious premise is captured perfectly by the term “money laundering”. It is not in and of itself a moral vice; it is bad only insofar as it enables primary crimes. Not much remains of “money laundering” when stripped of the primary crimes it enables and when considered independently of the state’s moral perspective. It is merely the practice of presenting a sum of money as having a mundane origin. Every single monetary transaction satisfies this description.

In other words, money laundering is a purely legal notion with no inherent bad (or good) ethical character.

This characterization does not excuse crimes enabled by money laundering. The point is rather that these crimes are already illegal, regardless of whether the perpetrators launder the proceeds. The judiciary does not need a second legal ground to sentence them.

Ordinances in relation to the prevention of money laundering – these include know-your-customer regulations that require financial service providers to verify customer’s identity and residential status, reporting requirements that turn financial service providers into informants of the state, and throttling or otherwise limiting the volume of transactions intermediated – have no inherent justification in and of themselves; they are better characterized as tools in the arsenal of law enforcement. Enforcing these ordinances, i.e., penalizing individuals and institutions that violate them, enables law enforcement to track down primary crimes or disincentivize them by making them unprofitable.

However, the question is not whether the means used to combat money laundering are effective tools for law enforcement; the question is whether they are appropriate tools for law enforcement. By the same token, indiscriminate wiretapping might be an effective tool for law enforcement, but might not be an appropriate tool. This question can be answered in two ways. First, there is the argument from deontology. It involves arguing from the perspective of human rights and civil liberties. Second, there is the consequentialist argument. It involves analyzing the consequences of competing policies and judging them based on how the consequences compare. A third way would be to argue from law, for instance by showing that established protections on civil liberties are inconsistent with recent money laundering countermeasures. This third strategy, however, is a category error. It can show at best that there is an inconsistency in the law, not how it ought to be resolved.

Deontology

The Right to Privacy

The individual’s right to privacy is affirmed by a litany of legal documents including the Fourth Amendment to the US Constitution, the Universal Declaration of Human Rights, and the European Declaration on Human Rights. These declarations are not mere legal fictions, but represent the best attempt by generations of war survivors to ensure that their sacrifices are not in vain. They did this by casting into legal effect timeless ethical principles, designed to serve as a bulwark for posterity against the crimes that defined their own times.

To deny individuals their right to privacy in the name of another, greater good is to reduce them to pawns on a utopian chess board. It is inhumane because it is inherently hierarchical: it makes the innocent individual subordinate to the plans of other individuals.

The position that individuals who have nothing to hide, have no need for privacy, is absurd for several reasons. It assumes that law enforcement is infallible and adheres to an impeccable moral standard. Even if that is true most of the time in most places, this absurd position asserts that it is true always and everywhere. More importantly, what constitutes “something to hide” is not an ethical question but a legal one. It can change at the behest of legislators and the executive branch, who are capable of making ethical mistakes which then cannot be appealed. Most absurdly, the assumption that a need for privacy can arise only from illicit behavior assumes that the individual is guilty unless proven innocent, without supporting evidence, and thus contrary to standard practice in criminal law.

Ownership Implies Untraceability

What does it mean to own something? The English language already makes a useful distinction between possession and ownership. Possession refers to actual control: someone possesses a scarce good if they are capable of employing it as means towards the accomplishment of their ends and capable of excluding others from doing the same.

The English language fails to make an equally clear distinction between two different meanings commonly captured by the term “ownership”. First is the legal concept, which might be more precisely denoted by the phrase legal ownership. It refers to the allocation of resources to persons that the state will enforce in case of dispute. Second is the ethical concept, which may be more precisely denoted by the phrase ethical ownership. It refers to the allocation that every person ought to respect, and by extension that the state ought to enforce even though it may sometimes erroneously undermine it.

It is important to stress that legal ownership and ethical ownership are distinct notions. Ethical ownership is a logically coherent and semantically solid notion independent of the state. Legal ownership is only relative to the state that enforces it, and distinct states often disagree about it.

In case of dispute, the principle for deciding ethical ownership of a scarce good is to trace its history across a sequence of transfers from consenting prior owners to consenting new ones. The chain of ethical ownership terminates at the point when the resource in question was last unowned, when the first owner acquired it from nature by mixing it with his labor.1 One might call this principle the Chain of Owners rule. No person can exercise a valid claim based on a broken chain.

To disagree with this principle is to provide a pathway for thieves to make their crime ethically acceptable. Whatever criterion or proviso overturns this principle is a target to be satisfied. For instance, if thefts that happen more than two years in the past should not be considered, then all the thief needs to do is to hold on to the loot for more than two years to become its ethical owner. If thefts that happen more than 10 transfers in the past should not be considered, then the first buyer only has 9 transfers left, and the next 8, and so on. The end-result of this process is ethically owned property, and every link in between the theft and the end-product has a monetary incentive to participate.

The Chain of Owners rule is certainly a good starting point, but it is unworkable in practice. In general, people have no idea about most of the historical ownership chains of the things they own. It is cumbersome to record a trail of ownership and even this record can be spoofed. As a result, law in practice must cut corners. This fact is embedded in the principle that possession is nine tenths of the law; according to this principle, the person in possession of an object of dispute is assumed to be its owner unless there is evidence pointing to the contrary.

If this Nine-Tenths principle were not in place, commerce and trade would be all but impossible. Both parties to an exchange would need to ascertain the traded goods’ histories in order to be capable of defending their new ownership claims in case of dispute. As a result, trades will only take place if the objects’ histories are available, or between the parties capable of tolerating the legal risk they incur if it is not. The legal risk is potentially losing the acquired goods to a third party claimant in a court of law whose guiding principle is more arbitrary because by assumption it does not favor the bearer.

This Nine-Tenths principle implies two things. It is not only practical for ownership to be untraceable, but necessary as well. It is practical because despite the untraceability, this principle offers a workable solution to resolve disputes via law. It is necessary because a documentable history is the one thing that allows the claimant to undermine the bearer’s claim, and simultaneously the one thing with which the bearer can refute the claimant’s challenge. Other things being equal, a difficult-to-trace object of contentious ownership induces a greater cost on the claimant because the threshold for evidence to overturn the Nine-Tenths principle is more difficult to reach. As a result, courts deciding ownership of easy-to-trace goods are biased not in favor of the ethical owner, but in favor of whoever employs the most resources to produce the more compelling history. Phrased concisely: traceability gives rise to an arms race of information to produce the stronger legal claim, whereas untraceability favors ethical ownership.

A premise in the above argument is that the ownership of the easy or difficult to trace object is in dispute. But the degradation in the capacity of the legal system to settle disputes fairly might be acceptable if there are fewer disputes to begin with. However, while traceability reduces the probability of a benign dispute originating from confusion about the ownership chain of an object, it increases the probability of a malicious dispute whereby the thief weaponizes disinformation about the ownership chain to trick the legal system into executing his theft for him. This type of legal attack is more likely because traceability makes it easier: every single link in the ownership chain is a potential point of divergence for the false branch to start from. In security terms, the wider attack surface benefits the attacker and puts the defender at a disadvantage.

The lack of support from a legal system that is at least systematically biased in favor of ethical owners strips the notion of “ownership” of a quintessential feature. Why would anyone acquire something valuable, only to let it pass to the hands of someone who is more adept at gaming the legal system? Why work at all beyond bare subsistence and immediate consumption, when there is no robust way to store the fruits of that labor? Without the support of the legal system, people have no incentive to own things whose possession they cannot personally defend. The feature that “ownership” loses is the very feature that sets it apart from “possession”.

The Right to Free Money

Money is the logical extension of one’s will, second only to conscious muscular movement. Every interaction is only a few hops downstream from some monetary interaction that enabled it. Money is the gateway through which individuals engage with society. What could be more personal than the profile of interactions of one individual with other members of society? If nothing, how can privacy have any meaning at all if it applies only to less personal things?

As I write this, I can think of two contending spheres of action and knowledge that might be comparably personal – although it should be noted that in both cases money is typically involved, and therefore both examples are typically contained by a person’s financial profile. The first example is the relationship between a client and his attorney. The second is the relationship between a patient and his doctor. In both cases the service provider has an ethical obligation, recognized by law, to respect the consumer’s privacy.

These relationships resemble those between a user and a financial service provider such as a bank or an investment platform. The user trusts the service provider to behave responsibly and in his best interest, and this trust is a precondition to the exchange. The ethical responsibility to protect the users’ privacy is implied by the power-of-attorney and fiduciary duty embedded in the service contract. This responsibility, however, is incompatible with anti-money-laundering ordinances which forbids financial intermediaries to serve insufficiently identified customers, and compels them to report their behavior to the state. Obviously, these ordinances go against the privileged banker-customer relationship. Its different status from the privileged client-attorney and patient-doctor relationships sets the worrying precedent for the latter two to be dismantled as well.

In the specific case of cryptocurrencies, the right to use privacy-preserving currencies is implied by the right to free speech. Participating in a cryptocurrency network amounts to downloading the software, installing and running it, and then sending and receiving messages to and from other participants in between local calculations. Aside from those local calculations, all steps are forms of communication over the internet. And just as free speech implies the right to critically assess the counterparty’s argumentation and evidence and to ponder the best argument in response, so too does it imply the right to use the adequate tool to aid in this computational task. Aside from the aid of computers, there is no categorical distinction between the critical thinking done by participants in a debate, and the verification-calculations done by participants in a cryptocurrency protocol. In short, to criminalize private cryptocurrencies is to criminalize some forms of communication or some forms of thought.

Against Free Money

Regardless of the classification of “money laundering” as denoting a purely legal and ethically void notion, ethical questions do remain in relation to enabling primary crimes. Specifically, the argument for the curtailment of the right to free money might be steelmanned into something like this:

  • Enablers of crimes are culpable for them.
  • The a) existence, b) legality, c) widespread use, and d) development and maintenance of private currencies, enable primary crimes by making them lucrative.
  • The curtailment of the right to free money is a proportionate response to the criminal actions of enablers.
  • The *ex ante* curtailment is a preventative countermeasure appropriate by virtue of its greater effectiveness than the *ex post* response.

It is a formidable ethical argument and a defense of private money would be incomplete without a rebuttal to it.

Enablers of crimes are culpable. To decide culpability we must look at the chain of causes and effects. The transporter who drives the bank robbers to and from the location of the crime, but who otherwise does not participate in it, may not be the proximate cause of the robbery but it is a sine qua non cause. Without the transporter, the crime would not have happened.

The problem with the above argument is that while culpability does propagate across a chain of causes and effects, it does not propagate well across a network of causes and effects. Elaborating on the above example: the taxi driver who serves the robbers in good faith and unknowingly enables the crime is not culpable. It could be true that without any taxis the crime could not have taken place. But culpability is an individual matter and not a collective one. If for whatever reason the particular taxi driver had declined the job, another one would have taken the fare instead.

It is unreasonable to charge the particular taxi driver with lack of due diligence unless there are obvious red flags indicating that the travelers are up to no good. If the taxi driver had practiced the due diligence that could have exposed the would-be robbers, he would be undermining his own business. In general, his clients will prefer the competing taxi driver who asks fewer questions.

To complete the analogy, criminalizing private moneys because they can enable crimes is like criminalizing taxis because they can enable them too. Charging the users of private currencies with partaking in an economy that enables crime is like charging taxi passengers with the same. Forbidding the development and maintenance of privacy coins is like forbidding the manufacturing and maintenance of taxis. Only individuals can be charged with enabling a crime, not classes of individuals, and only based on specific evidence pointing to a cause and effect relation that implicates them.

Contrary to what law enforcement might like to suggest, the mere fact that someone uses privacy enhancing technologies does not constitute evidence of wrongdoing or cover-up. The space of ethical uses of privacy-preserving technologies, including private money, is not constrained by the imagination of law enforcement officials – or by that of privacy advocates, for that matter.

Consequence

An argument about the desirability of anti-money laundering ordinances based on consequences must be rooted not in idealism but in pragmatism. Policies should be judged based on their efficacy relative to a stated objective, as well as based on their cost-benefit profile. Ineffective policies should be rejected, as should policies whose costs outweigh benefits.

It is possible that efforts to combat money laundering generate more tax revenue than they cost. But the reverse is also possible, in which case the anti-money laundering efforts cost more than the additional tax revenue they generate. There is no central manager who needs to answer for this loss, no stockholders to explain it to, and no incentive to correct this seemingly irrational behavior.

Granted, the objective may be to reduce other crimes and not just tax evasion; primary crimes such as extortion and human trafficking that are enabled by money laundering. Relative to this objective, it may be justifiable to run a net loss in terms of government budget. The obvious questions then are a) how effective are these policies and activities at eliminating the targeted primary crimes; and b) how much budget does that effect justify?

What Amount of Crime is the Right Amount?

Fighting crime, not just primary crime but money laundering also, is a process of diminishing marginal returns. Doubling the resources allocated to the fight will not double the effect. It is conceivable and not unlikely that the complete eradication of the targeted primary crimes, whether through money laundering countermeasures or through more direct measures, costs more than the country’s gross domestic product. Complete eradication is an untenable objective; instead of irrationally hoping to achieve it, we must decide how much crime we are willing to tolerate in order to continue living in a prosperous (and free) society.

The war on drugs is an instructive example. Despite being illegal for the general population, hard drugs routinely find their way into prisons.2 Clearly both the demand and supply exist despite active measures from the prison guards and police to prevent the trade of drugs on their watch. By doubling their efforts, the guards can at best affect the supply but not the demand; and as a result the market will find a new, higher, market clearing price.

Perverse Consequences

The war on drugs is an instructive analogy in another important way: it exemplifies an argument showing how violent crime might increase as a result of criminalization. Government edicts cannot erase demand; at best they can affect supply and drive the market underground. In this underground market there is no quality control. Participation in this market is risky. There is no court that can settle disputes peacefully. And so when disputes do arise, the parties have every incentive to settle them with violence. Moreover, illicit drug dealers make a premium relative to a fully legalized market; a portion of this premium inevitably goes to fund the mechanisms of dispute resolution.

The analogy is not perfect because in the case of money laundering, the good or service being demanded is the state imprimatur that authorizes funds with obscure origin for use in settling debts. There are no non-state suppliers; the state has a monopoly on this good. Nevertheless, as demand persists, the market remains. The consequence is two-fold.

First: buyers pay the price, which they perceive to be filling out the right forms, jumping through the right hoops, wording the agreements in the right language, structuring the legal entities correctly, and of course paying expensive consultants to tell them how to do all this. The state, oblivious to market dynamics, and observing failure on its part, redoubles its efforts to make money laundering harder still. This interplay devolves into an arms race with ever more clever techniques to make money appear legitimate and ever more stringent countermeasures hoping to distinguish good money from bad.

Second: the end-result of this arms race is a firewall between white money and black money that is too expensive to overcome for small players, even if their funds have no link to the primary crimes that money laundering countermeasures are supposed to reduce. The financial institutions whose scale enables them to receive regulatory approval are isolated artificially from the smaller but otherwise more efficient competition. This regulatory approval reinforces the discrepancy in scale.

A lot of things fall into place when the discussion about money laundering is viewed from the perspective that large financial institutions are looking for a cudgel to beat smaller, otherwise more efficient upstarts down.

Foregone Prosperity

Know-your-customer regulations and other anti-money laundering ordinances represent a costly obstacle to be overcome. They prevent money from moving about freely, even when it has no ties to primary crimes. Individuals and institutions prefer to keep their capital passive rather than complying with the onerous requirements. As a result, less money is at work contributing information about supply and demand to the global pricing mechanism and thereby increasing the division of labor. Less capital is available to entrepreneurs who seek new and more efficient ways to make consumers happy. Reduced to one phrase: we are less prosperous as a result of anti-money laundering ordinances. And its corollary: private money will make us more prosperous.

It is difficult to quantify the magnitude of the lost opportunity because it is both abstract and unseen. But here is a thought experiment to make the argument a little more concrete and qualitative: imagine how much more money would be available for researching cancer cures, if investors were able to collect dividends anonymously from profitable pharmaceutical ventures.

Legitimate Uses

There are uncontroversial use cases for private money.

Privacy is a defense mechanism against theft. People who leave a trace can show up on the radar of thieves. Jameson Lopp maintains a database of news articles covering physical attacks on Bitcoin holders. The attackers in question were not random robbers but thieves with targets. Know-your-customer requirements will ensure that this list keeps getting extended by providing attackers with the names, home addresses, and copies of identity documents of unwitting targets. Even Ledger, one of the leading hardware wallet manufacturers, got hacked – resulting in the leakage of their customers’ names and addresses. If Ledger cannot keep their database safe, who can?

Charity organizations often receive anonymous donations. There are at least two reasons for this. First, the donor does not want to be on record, only to be approached again by the charity or by another charity for more donations later on. Second, true charity means not using the donation as a means to launder one’s reputation. Anti-money laundering ordinances attach a name to all charity donations, and will result in less of it.

Investigative journalism is subversive by nature. It sheds light on crimes and vices against the will of vested interests who would prefer to keep them in the dark. One of the ways these vested interests fight it is by going after the source of funding that supports either the investigative journalist or the publication venue. The effect is compounded when modern cancel culture is weaponized. This is not just a use case for journalists and news media to use private money, but for their supporters as well. Private money supports free speech in a very concrete way. Anti-money laundering ordinances expose donors who support free speech with their wallets to attacks by proxy.

Alternative to Fiat

Launched in the wake of the 07-08 financial crisis, Bitcoin was originally conceived of and popularized as an alternative to established financial intermediaries and central banks, and in protest to the system of fractional reserves, bail-outs, and government stimuli – the *fiat monetary system* for short. Bitcoin, as well as the long list of alternative cryptocurrencies that followed, represents an asset class that competes with fiat money. While this feature is not unique to private cryptocurrencies, it is one they inherit.

The use case of cryptocurrency that this section alludes to comes from its inherent monetary inflexibility. It protects the bearer against the trickle-down effects of a fiat monetary system without participating in it. It does this in the same way commodities do it, but without sacrificing liquidity. Cryptocurrencies can literally be sent at the speed of light without the need for trusted intermediaries.

The corollary of this use case is the fact that cryptocurrencies are in competition with fiat currencies. The more demand there is for cryptocurrencies, the less demand there is for fiat, and the less power central banks and financial players have over the economy. The existence of fiat currencies is an effective counterweight to the fiat monetary system.

Given the adversarial nature of the relationship between fiat money and cryptocurrency, the concern uttered by beneficiaries of the fiat monetary system about money laundering should not be mistaken for altruism.

Insulation from Legal Risk

By far the most compelling legitimate use case for private money is insulation from legal risk. Stolen assets should be returned to the proper owner. Traceable money can be proven more easily to have been stolen if it was, but it is also more conducive to supporting spurious claims of theft. What happens when an institution that holds traceable cryptocurrency on their balance sheets, discovers, based on information that came to light only after acquiring them, that the digital coins are actually downstream from a well-documented hack that happened years earlier? What happens when they are sued to return the stolen assets to their proper owner?

A legal defense based on having received the coins in good faith (bona fide) is comparatively easy to undermine by a claimant who pours resources into listing the many red flag indicators of theft that the institution allegedly chose to turn a blind eye to. Depending on your perspective, the other hand of this comparison can be one of two things. It could be a legal defense rooted in plausible deniability, which shifts the burden of proof from defendant to plaintiff. The plaintiff now has to prove that the coins in the defendant’s possession are the same ones that had been stolen earlier. No privacy-preserving currency can support such a claim. Alternatively, the other hand of the comparison is the absence of any need to defend anything at all in court because the claimant does not know whom to sue precisely because he cannot trace the stolen coins.

Anti-money laundering ordinances not only make it difficult for institutions to acquire and hold privacy-preserving currencies, they also render whatever privacy they do provide moot by supplementing them with a trace of ownership history. Complying institutions are incapable of insulating themselves from the legal risk of holding cryptocurrencies. As a result, they are deprived of the use of a politically neutral, internet-native medium for settling international debts.

Crawfurd v. the Royal Bank

The claim that money be returned to the proper owner has an interesting legal precedent in Crawfurd v. the Royal Bank. In this history, Mr Crawfurd had sent two 20 pound notes in the mail, but these had gone missing. Having recorded their serial numbers, he notified the Royal Bank with the request to return the notes if they should be found. Shortly after, the Royal Bank discovered one of the notes and informed Mr Crawfurd. However, the bank refused to return the note because in their eyes it belonged to the bearer, which in this case turned out to be the Bank of Scotland.

A court case ensued. Mr Crawfurd’s claim was that no-one can acquire a property title through theft; and that therefore the Bank of Scotland’s claim of ownership was invalid. The banks argued that this principle would undermine the whole point of paper money, which is to make commerce easier. If whoever bears a note and whoever owns it can be different persons, and if the bearer must return it to the proper owner, then everyone who comes into possession of bank notes in the course of commercial activities must first verify that they are receiving them from their proper owners. To do this, they must be made aware of the entire history of the notes since they were minted. This task is so expensive it would all but make commerce unviable.

In the end, the judge sided with the banks. This case and ruling set the stage for other European economies and eventually the rest of the world to adopt similar principles.

I draw two observations from this legal anecdote.

First: fungibility was not an inherent property of the goods in question: two bank notes of the same denomination were not interchangeable. The legal system was required to compensate for this deficiency by simulating through law a property that was understood at the time to be an essential quality of money: fungibility.

Second: a passage of Roman law cited in defense of Mr Crawfurd’s case sheds lights on how the Romans thought about private money and theft. From the same article:

“Should another’s coins be paid, without the knowledge or volition of their owner, they remain the property of him to whom they belonged; should they have been mixed, it is written in the books of Gaius [Cassius Longinus] that should the blending be such that they cannot be identified, they become the property of the recipient so that their [former] owner acquires an action for theft against the man who gave them.”

In other words, according to the Romans, a claim of ownership of stolen coins extends in the future only as long as they can be identified. After the point at which they can no longer be identified, the original owner has a claim of theft against the thief; and the coins belong to whoever bears them.

Geopolitical Schelling Point

There is no international rule of law. Between states there is only war or diplomacy, but no higher authority to appeal to. The world is adversarial and there are no supreme courts.

In order to prefer commerce over isolation or war, states and multinational corporations need a globally accepted bearer asset to settle debts with. This asset cannot be controlled by any one party, because then it could be weaponized.

Gold served this purpose for centuries, but it has drawbacks in today’s hyperconnected world economy. It is difficult to move and expensive to assay; and thus liable to confiscation, blockade, and fraud. Cryptocurrencies solve these issues, but the traceable ones throw out the baby with the bathwater by exposing the bearer to legal attack vectors. Privacy-preserving cryptocurrencies are the natural Schelling point for a financial backbone of a multipolar world order.

The technology has been achieved and cannot be unachieved. The genie is out of the bottle and the transition is underway. States that fight private money risk undermining their own geopolitical interests. States that embrace private money will see their financial sectors boom.

On Nonlinear Noisy Key Agreement

TL;DR. A large number of post-quantum key encapsulation mechanisms (KEMs) and public key encryption schemes (PKEs) rely on noisy linear algebra problems. Interestingly, the addition of noise to make otherwise easy problems hard, is a strategy that remains restricted to linear algebra and fails to extend to nonlinear operations. This article explores why.

Noisy key agreement

Key agreement is a protocol by which Alice and Bob each send one message to the other and end up agreeing on a shared secret key. The eavesdropper Eve, who observes all messages in transit (but can’t modify them) remains incapable of computing this secret. The first such protocol was introduced by Diffie and Hellman and bears their names, but the general principle extends to generic algebras and not just commutative group theory.

For instance, let Alice and Bob agree on a common random integer G from a finite ring R, such as e.g. the set of nn matrices of integers modulo some prime p. Moreover, let Alice and Bob each sample their secret, a and b respectively, from this structure as well. They then exchange â = aG and b̂ = Gb, allowing both to agree on the shared key k = ab̂ = âb = aGb. Note that while the order of multiplication is important for matrices, by agreeing beforehand whose secret will be multiplied on which side of G, Alice and Bob circumvent this complication entirely.

Unfortunately, this protocol is completely insecure. Eve, who sees Alice and Bob agree on G before sending â = aG and b̂ = Gb, can compute G-1 and recover both Alice’s and Bob’s secrets, not to mention the shared secret key. Even if the ring disallows efficient computation of an element’s inverse, it remains extremely likely that there is a way to find the solution b to the system of linear equations Gb = b̂ and symmetrically for a.

The solution that makes the protocol a noisy key agreement protocol is to transmit only an approximation of aG and Gb. To see why this makes Eve’s task hard, observe how the error term 𝝐b = b̂ – Gb explodes: G-1b̂ = G-1(Gb + 𝝐b) = G-1Gb + G-1𝝐b = b + G-1𝝐b . Since G is a matrix with uniformly random coefficients, so is G-1 and multiplying that by another matrix 𝝐b — even if it has small coefficients — yields another random ring element that hides b much like a one-time pad.

However, the addition of small noise makes it difficult for Alice and Bob to agree on the same secret. Observe that Alice computes ka = a(Gb + 𝝐b) whereas Bob computes kb = (aG + 𝝐a)b. The trick is implied by the symbols’ case: instead of sampling uniformly random a and b, Alice and Bob sample a and b with small coefficients. If a, b, 𝝐a, and 𝝐b have small enough coefficients, then Alice’s view ka = aGb + a𝝐b is approximately the same as Bob’s view kb = aGb + 𝝐ab. As long as the difference a𝝐b – 𝝐ab is small enough, they can proceed to agree on an exact key with one additional message which either reconciles the two views or uses them in combination with error-correcting codes to transmit a wholly new message. In this last case, I like to refer the views ka and kb as shared noisy one-time pads or “snow-tipis”.

So how small should the secret elements a, b, 𝝐a, 𝝐b be? On the one hand, the secrets should not be too small because that reduces Eve’s search space. On the other hand, the secrets cannot be too large because then the difference a𝝐b – 𝝐ab is too large to enable either the reconciliation or transmission strategy. The situation is best described visually. While the unknown bits of the secrets do spread and multiply — and obscure Eve’s view — they also leave some bits of aGb intact; these bits can then be used as secret key material.

Incidentally, Ramstake, my own submission to the NIST PQC Project, does not quite follow this “intact bits” strategy of establishing common secret key material. Instead of having a few unknown bits at fixed locations, the secrets now have a few flipped bits at unknown locations. As long as the difference a𝝐b – 𝝐ab is not too dense, an error correcting code can help extract or transmit secret key material. Interpreting a darker shade of grey as representing a denser error distribution, this gives rise to the following analogous diagram.

 

Nonlinear Noisy Key Agreement

So why are there no nonlinear noisy key agreement protocols, or cryptosystems based thereon? Actually, that premise is not true. There is a submission to the NIST PQC project by the name of CFPKM whose underlying hard problem is polynomial system solving with noise (“PoSSoWN”). Alice and Bob compute their protocol contributions by evaluating a quadratic function f, which has small coefficients, in their secret vectors sa and sb, also with small coefficients, and by adding another small noise term. The underlying protocol is shown in the next figure. Unfortunately, despite the security proof, the cryptosystem was broken within weeks of the submissions’ publication.

The cryptanalysis exploits the observation that the keys computed by Alice and Bob differ only by the difference of element-wise products f(sa) ⨀ e2f(sb) ⨀ e1, which affects only the lower bits; whereas the high bits of both views are used for the session key. Importantly, these high bits are the same in b1b2, which is a value the passive adversary can compute as well.

So why is there no successful cryptosystem based on noisy nonlinear key agreement? The first observation is that the term nonlinear is really only relative to what the function’s arguments are. For instance, the expression x12 + 2x1x2x2 is nonlinear as a function of (x1, x2) but linear as a function of (x12, x1x2, x22, x1, x2, 1). By extending as we did here the vector of arguments of a function to a vector of all monomials occurring in that expression, any expression can be regarded as a linear function. In particular, both Alice’s and Bob’s computation of their proper views of the noisy secret key may be considered as linear transforms on some extended vector of monomials. This observation suggests a two-step approach to the diagrams above that indicate the source of secret key material: the second step captures the familiar linear noisy key agreement. The first step captures the extension of the original arguments into a vector of monomials.

This diagram highlights the origin of the problem: in order for there to be usable secret key material left at the end, the unknown bits in the extended vector of monomials must not be too many. In order for those unknown bits to not be too many, the unknown bits in the original arguments must be even fewer. However, this very salient feature makes these original arguments a vulnerable target for attack.

Conclusion

Why are there so few cryptosystems based on nonlinear noisy key agreement? My answer is twofold:

  1. Because any such protocol implies a linear noisy key agreement protocol.
  2. Adding nonlinearity to a linear noisy key agreement protocol makes it less secure.