I am not an expert in this subject area. I am simply trying to get some of my thoughts on "paper" so to say, as it helps me organize them (especially when revisiting them later). This is not intended to be a well-organized article.

The Problem

Bitcoin typically uses ECC keys to derive addresses and sign spend transactions. But it actually allows for nearly any method of creating addresses and verifying authorization to spend a transaction. When a transaction sends coins to an address it includes a Bitcoin Script; the script is a Bitcoin proprietary non-turning complete language used to verify a later transaction that would try to spend the coins in the current transaction. Simply, each transaction sets up the rules by which the receiver can spend the coins they receive. Currently only certain Bitcoin Scripts are accepted to limit the possibility of someone accidentally sending coins to an unspendable death (it a completely valid script could simply deny anyone the ability to spend the coins; similarly a different script could allow anyone to spend the coins). The reason this script was invented and used was to allow the Bitcoin network to integrate different methods of public-private key signatures. As noted previously, ECC is the predominate signature method today - but ECC is suceptable to Shor's Algorithm on Quantum Processors. Last I hear non-fuzzy quantum processors were up to 7 qubits (fuzzy processor, like those developed by D-Wave, cannot run Shor's Algorithm). At some point quantum processors will contain enough qubits to break the 256-bit ECC keys of Bitcoin.

The problem is somewhat mitigated because Bitcoin addresses are not the public key of the key pair, but instead a hash thereof (a SHA256 hash derivative). When coins are first send to an address the private key is not leaked, therefore an attacker would have to first break SHA256 (no known vulnerability exists at this time, though the NIST had a competition to develop SHA-3 because of perceived weaknesses in SHA-1 and SHA-2). The public key is published the first time coins are spent from an address however. An immediate workaround to the Quantum problem is to never re-use an address once coins have been sent from it - while highly inconvenient it is also potentially susceptible to transaction tampering if the ECC key could be broken before the next block (Bitcoin contains a function to "revise" transactions before they are finalized by inclusion in a block). At some point in the distant future it's likely that quantum processor will become fast enough to pull off this kind of attack. A better protection is to change the signature algorithm to something quantum processors cannot break in the first place.

The field of Post-Quantum Cryptography is relative new, starting only in the late 80s and early 90s. Since then there have been a number of advancements, though not without drawbacks. Hash based schemes, such as Merkle Signatures can only be used once. ECC code-based schemes have key sizes nearing a megabyte, compared to ECC's 256-bit keys, these would require a bit more storage. Elliptic Curve Isogenies are an interesting idea, essentially messing with the basic math algorithms but retaining the formulas of traditional ECC. What I believe are the most promising, Lattice-based cryptography.

Solution 1 - Hope for the Best

As mentioned above, ECC's public key isn't revealed until the coins in an address are spent. This means that ECC addresses could be used until a spend transaction has been processed for that address. After a single spend transaction the address would have to be considered susceptible to attack and discarded. Also mentioned above, there is technically a time period between the transaction being published a being included in a block where an attacker with a sufficiently fast quantum processor could break the ECC private key and broadcast a revised transaction. The key takeaway from this "solution" is that it's a temporary band-aid while a secure algorithm is developed.

Solution 2 - Lattice Cryptography

Lattice cryptography is at the same time overwhelmingly simple and complicated, depending on a variety of factors. I'll not try to explain it here as... well I'm lazy, and it doesn't matter so much to the point I'm trying to make. if you really want to know the basic idea behind lattice cryptography there are a number of good books and various published papers available on the subject. The important points are: 1. keys have traditionally been too large to be practical, in the order of several kilobytes - 10 to 20 times larger than a typical ECC key. 2. Plain lattices can usually be reduced by the LLL algorithm, which essentially sucks an extraneous data out of your security algorithm and makes the system significantly easier to break.

NTRU is an interesting lattice based encryption scheme. Without going into detail of how it works let's just jump straight to what it has to offer and why Bitcoin should never use it. Being lattice based NTRU is not susceptible to Shor's Algorithm or other quantum processor shortcuts (quantum processor could still be used like traditional processor to brute-force the keyspace, as is the case with all PQ-Crypto). The key sizes are in the 1-2 kilobyte range for keys with roughly the same security as ECC-256, notably larger but a size we can work with (also, when receiving coins only the hash of the public key is used, so your Bitcoin address would still be roughly 27-34 characters. The real problem with NTRU is that it is not a zero-knowledge signature system. NTRU was based on GGH, a very similar cryptographic algorithm with a major problem. Apply LLL lattice reduction a set of GGH signatures (in the order of dozens to hundreds) would reveal the private key. NTRU has improved upon GGH in a number of ways, especially in using perturbations (small errors purposely introduced to a signature to disguise the leaked private key knowledge). These techniques significantly improved NTRU's resistance to lattice reduction, but a modified technique called the NR attack still breaks NTRU signatures with a larger set of signatures (several hundred). This does mean that NTRU signatures could be used a limited number of times with some safety, but additional research could make the attack more efficient, and there is no reasonable way to estimate the exact number of signatures that could be considered safe to use.

Next on the list of candidates is a promising set of Lattice Ring with Error algorithms which were recently published by Vadim Lyubashevsky, Chris Peikert, and Oded Regev. Their research has primarily been on lattice rings of the form Ζ[x]/Φ_m(x). That mess is mathematical notation for a family of equations, one simple example might be 2x²+3x. What the math looks like really isn't relevant to it's practical application however. What's important is that these equations combine the strength of the discrete logarithmic problem, the simplicity of ElGamal (aka DSA), and the quantum resistance of Lattice math. The biggest drawback at this time is that the scheme has not been extensively cryptanalysed; there is some chance that a LLL or NR like attack might significantly weaken the cryptographic strength of the algorithm. Lattice problems in general are commonly susceptible to reduction type attacks, usually modifications of LLL. To defend against reduction the algorithm incorporates errors (or perturbations). When checking a signature an error is expected, but is also expected to be within a small limit. At the same time this error becomes cumulative when analysing a set of signatures in an attempt to recover the private key. The attack on NTRU requires significantly more signatures when perturbations are incorporated, though with enough signatures the perturbations tend to average out.

In the next article on post quantum cryptography I hope to show a simplified signature scheme based on Ideal Lattices and Learning With Error over Rings mathematics. I only have a BS Minor in Math, so it takes me a bit to work through the general case to a workable example.