https://bitcointalksearch.org/topic/m.5540305
For the laymen, most public key cryptography (e.g. RSA and Bitcoin's ECDSA and Zerocoin) is based on number theoretic assumptions such as the difficulty in factoring discrete logarithms which makes them impossible to crack (at sufficient bit lengths) with current computers. However, quantum computing would (in theory) enable Shor's algorithm which reduces these factoring problems from exponential to polynomial time. Thus what would have required a zillion years to crack can be cracked in reasonable time to make it practical.
However, cryptographic hash functions do not rely on number theoretic assumptions. Instead they rely on the assumption of asymptotically perfect random distribution of the input to the output, which can be somewhat verified like this. Thus they can't be cracked with Shor's algorithm and only Grover's algorithm can be applied with a quantum computer. Thus they remain exponential time, and only the bit lengths (exponents) get effectively halved.
Lamport signatures use only cryptographic hashes. One of the problem with employing them in a blockchain has been they take up much space (either for the public key or the signature or both), but I just published a discovery in my prior post which enables making them smaller in exchange for more computation.
This discovery makes Lamport signatures more practical for blockchains than they were before, but still they are not as small as number theoretic public key cryptography.
Unfortunately I don't think this will work for Bitcoin, at least not until they implement pruning of the UXTO, but it can work in an altcoin.
I currently see no way to make Zerocoin resistant to Shor's algorithm, but I am still researching this. But Zerocoin is mostly useless any way because of pattern analysis on coin amounts.
However, cryptographic hash functions do not rely on number theoretic assumptions. Instead they rely on the assumption of asymptotically perfect random distribution of the input to the output, which can be somewhat verified like this. Thus they can't be cracked with Shor's algorithm and only Grover's algorithm can be applied with a quantum computer. Thus they remain exponential time, and only the bit lengths (exponents) get effectively halved.
Lamport signatures use only cryptographic hashes. One of the problem with employing them in a blockchain has been they take up much space (either for the public key or the signature or both), but I just published a discovery in my prior post which enables making them smaller in exchange for more computation.
This discovery makes Lamport signatures more practical for blockchains than they were before, but still they are not as small as number theoretic public key cryptography.
Unfortunately I don't think this will work for Bitcoin, at least not until they implement pruning of the UXTO, but it can work in an altcoin.
I currently see no way to make Zerocoin resistant to Shor's algorithm, but I am still researching this. But Zerocoin is mostly useless any way because of pattern analysis on coin amounts.
