How does IOTA make itself resistant to quantum computing based attacks?

Question

IOTA has been described as "quantum resistant" (not "quantum secure"). What steps did the developers take to make the protocol resistant, and are there further steps that need to be taken in the future?

Answer 1

IOTA does not use traditional asymmetrical (public-key) cryptography algorithms which depend on not being able to efficiently computing discrete logarithms or factoring numbers (which are believed to be easy on a quantum computer).

Instead, its signatures are based on the Winternitz signature scheme (slightly modified for ternary) which only depend on the impossibility of reversing hash functions (Kerl in case of IOTA which is Keccak with its inputs and outputs converted to ternary), which is believed not to be that as easy on a quantum computer as factoring a number (although any reversing of a (hash) function can be done more easily on a quantum computer than a traditional computer).

Disadvantage of Winternitz scheme is that signatures are one-time (every signature reveals parts of your key); therefore users have to be careful not to reuse addresses that have been spent.

Answer 2

Just completing a response from the mihi:

Since all Iotas have already been created on genesis, it's impossible to "mine" Iotas and take advantage of a quantum computer to do this.

Iota is resistant to spam attacks because it forces users to validate two transactions before making one. Spam attacks have been a big problem on the Bitcoin network lately. There are no fees on transactions, there is no way the network suffers with a rate increase. Understanding this is the first step in understanding resistance to quantum computers.

The more technical explanation is contained within the Iota white paper. Since this was too big for a comment, I'll quote it here:

The process of finding a nonce in order to generate a Bitcoin block is a good example of such a problem. As of today, in average one must check around 2^68. nonces to find a suitable hash that allows to generate a block. It that a quantum computer would need O(sqrt(N)) operations to solve a problem of the above sort that needs O(N) operations on a classical computer. Therefore, a quantum computer would be around sqrt(2^68) = 2^34, this is approximately 17 billion times more efficient in Bitcoin mining than a classical one. Also, it is worth noting that if blockchain does not increase its difficulty in response to increased hashing power, that would lead to increased rate of orphaned blocks.

Observe that, for the same reason, the "large weight" attack described above would also be much more efficient on a quantum computer. However, capping the weight from above would effectively fence off a quantum computer attack as well, due to the following reason. In Iota, the number of nonces that one needs to check in order to find a suitable hash for issuing a transaction is not so huge, it is only around 3^8. The gain of efficiency for an "ideal" quantum computer would be therefore of order 3^4 = 81, which is already quite acceptable (also, remember that O(sqrt(N)) could easily mean 10 sqrt(N) or so). Also, the algorithm is such that the time to find a nonce is not much larger than the time needed for other tasks necessary to issue a transaction, and the latter part is much more resistant against quantum computing.

Source: IOTA WhitePaper

Basically, Iota acquires its resistance to quantum attacks reducing the difficulty of the PoW. So the advantage of a quantum computer to a normal computer is decremented.

There is one more factor to be cited. Bitcoin uses Elliptic Curves Cryptography or ECC (It is not resistant to the Shor's algorithm ). It is theoretically possible to make a brute force attack on any Bitcoin wallet (remember that the balances are public at Blockchain and there is an "economic incentive" to do this). The attack had reduced the complexity of O(N) to O(sqrt(N)). It is a difficult attack to do and it would depend on a little luck. But it is enough that a fragility is found in the ECCs so that this is further reduced.