Why did QAN choose lattices?
Read about the reasons why QAN’s Head of Cryptology Silur, ex-Ethereum, Zcash and Monero contributor chose lattices to create the quantum-resistant blockchain platform.
First, they are much more efficient on hardware. This is most important in our world of security vs UX wars. One of the reasons why we don’t have truly industry-ready (Sorry Trezor, Ledger) hardware wallets with proper key handling is that scalar multiplication (even with Montgomery) and especially point inversion on elliptic curves are extremely (energy) inefficient. There are still some improvements on the matter like the AMNF but they still can’t compete with the efficiency of LWE or RLWE. In most cases, these two primitives can fit into 16-bit memory (a common RLWE base constant is 59393 < 2¹⁶) and they are HIGHLY parallelizable. For example, LWE and SIS primitives solely rely on (modular) matrix multiplication and RLWE on polynomial multiplication which is even more parallelizable with the NTT (finite field fast Fourier transform).
Besides being CPU and memory friendly, these methods are the swiss army knives for the most interesting cryptographic magics of our time like fully homomorphic encryption which allows us to arbitrary operations on encrypted data (hello GDPR), identity-based encryption which I believe could solve one of the biggest obstacles in mass blockchain adoption, Indistinguishably obfuscation which would make companies like Denuvo obsolete for it’s the first secure method of software obfuscation. Another interesting theoretical advantage that made most cryptographers fall in love with Lattice constructions is that finally, you can utilize Gaussian sampling in your security “proofs” which is much more friendly in terms of reasoning than uniform distribution. Formally, If you sample a vector from the lattice with discrete Gaussian distribution and re-map it into the fundamental parallelepiped of the lattice it is statistically “crypto-close” to uniform distribution. This is really important in our work since there’s not really much surface to grab uniform distribution in itself, it’s the ideal model for security but the other edge of this sword that you can’t argue about it well. In contrast, Gaussian distributions are used in various other areas of the academy and there’s a lifetime’s worth of literature in statistics on them.
A biased view of quantum computation on blockchains
Argument 1: We need much more qubits to break a practical encryption system
Indeed there is a minimum bound of qubits to factor a number with Shor’s algorithm but Shor’s original algorithm relies on highly reliable (error-correcting wise) qubits. There are advances on relaxing the original and very restrictive requirements of Shor and a recent research from google promises to factor a 2048bit RSA number in 8 hours with a fictional 20 million qubits. This number is still fictional yes but I stress again that the more you keep distance from “well-entanglement” of your qubits, the cheaper your costs become and this attack is already a hundred times more space-efficient than prior methods. It’s much more (cost)effective and practical to handle more qubits that are more error-prone (see D-wave’s advances) than their counterparts with advanced error-correction.
Argument 2: But SHA is still safe, bitcoin won’t be affected
I handle this argument with an analogy: You are on the highway in your car. One of your tires blows out. Will you really keep going on with the excuse that the other three is perfectly working?
Indeed, SHA256 and especially SHA3 can be considered quantum-safe for Grover’s search in itself is not enough to attack functions that are only length-regular. There’s a research covering the practical costs of executing Grover’s search for an SHA preimage attack and it showed that the finite coherence time of logical qubits is still too much of an obstacle for it.
But it does not mean ANYTHING on Shor’s (or rather, it’s more practical variants) algorithm security-wise. There are only a small handful of protocols (if any?) where a hashing in itself is capable of holding UC (universal-composability) security where the underlying asymmetric scheme is assumed invertible. For example, in every ECDSA signature, it’s basic algebra to recover one’s public key from a signature, so the argument that your public key is protected behind a (or double) SHA is irrelevant. Also, there are many addresses (as of 2018 June 4, 19% of all Bitcoin addresses holding 36% of the market cap) linked to public keys on various off-chain channels, most likely in every custodial wallet.
Also, it’s still ongoing research to find the exact bounds of a quantum-circuit implementation (not Preimage-search) of SHA and whether the inherent reversibility of quantum-computations means anything on the matter. (Note there are known bounds for SOME kinds of quantum-circuits regarding SHA but no general results).