For public-key cryptosystems based on integer factoring and the discrete logarithm problem, the focus of quantum algorithms research to date, inspired by Peter Shor’s elegant discovery, has been on optimizing algorithms that can break an instance of the cryptosystem, i.e., solve for a private key given a public key, with a single run of the quantum computer.
That may be asking too much of a quantum computer, given the primitive state of implementation.
It may be better to ask instead, what is the minimum that a quantum computer needs to do in a single run, in order for an overall algorithm — including the portion run on a classical computer — to break a cryptosystem?
For the discrete logarithm problem, that question has a well-established answer from research over 30 years ago by Manuel Blum and Silvio Micali.
In their foundational paper on pseudorandom generation, Blum and Micali showed that the discrete logarithm problem could be solved efficiently given a “magic box” that computes the most significant bit of the discrete logarithm with a slight advantage over guessing.
That’s a potentially much easier problem to solve on a quantum computer (though still complex). Rather than solving for a full discrete logarithm nearly perfectly in a single run, the quantum computer would only need to solve for a single bit of the discrete logarithm, and only approximately on average.
As shown in the attached paper, it appears to be possible to realize this magic box with an improvement of Michele Mosca and Artur Ekert’s variant of Shor’s algorithm.
It’s not clear at this point how much benefit, if any, this new quantum magic box will have in practice. However, the new algorithm offers another approach for the ongoing optimization of quantum algorithms for breaking the discrete logarithm problem over both finite fields and elliptic curves. The reader is encouraged to analyze, improve — and find flaws.
— Burt Kaliski
Quantum Magic Box 