3 ms·

Thanks for the info. I forgot about the Grover speedup. I think it would still be amazing to get 2^64 operations on a 128-qubit quantum computer to break curren

by bdhe 13y ago

Thanks for the info. I forgot about the Grover speedup. I think it would still be amazing to get 2^64 operations on a 128-qubit quantum computer to break current 128-bit schemes. It seems like quite a tall order. Does using Shor to attack EC discrete log require us to work in the group of integers mod p? If it can work with the generic group then you might not need to go beyond 160-qubits. (But all of the above reasoning is based off the wiki article, so I might be mistaken.)

pbsd 13y ago
You work modulo p, yes, but the group is the set of points of the curve. The qubit bottleneck seems to be the Extended Euclidean Algorithm to perform modular divisions, which requires the greatest amount of space. Check [1, §6.2] for details. [1] http://arxiv.org/abs/quantph/0301141 http://arxiv.org/abs/quantph/0301141