Curator's Take
This fascinating theoretical work explores whether Regev's quantum reduction could provide an alternative quantum approach to solving the discrete logarithm problem, which Shor's algorithm already conquers but through entirely different mathematical machinery. The researchers cleverly use the Cheng-Wan reduction to create a testing ground for Regev's method, essentially asking whether this promising quantum technique can handle problems we know are classically hard but quantumly tractable. While their analysis shows current implementations fall short of the theoretical threshold needed to crack discrete logarithm, this represents important foundational research into the boundaries and potential of quantum algorithmic techniques beyond the well-established Shor's algorithm. The work contributes valuable insights into both the power and limitations of quantum reductions in cryptographically relevant problems.
— Mark Eatherly
Summary
We revisit the reduction of Cheng and Wan, which transforms instances of the discrete logarithm problem (DLOG) over finite fields into a decoding problem for Reed--Solomon codes, and study how Regev's reduction can be used to solve these instances. Regev's reduction turns a decoder for a code into a quantum solver for a decoding problem on the dual code. The quantum advantage depends on the dual problem being classically hard, which has proven difficult to establish. The Cheng--Wan reduction offers a natural source of such instances: solving them would solve discrete logarithm. Since Shor's algorithm already solves discrete logarithm, the goal is not a new quantum speedup but to understand whether Regev's reduction, applied to a problem we have independent reasons to believe is hard, can solve discrete logarithm, and if not, where it falls short. We generalize the hardness consequence of the Cheng--Wan reduction for Reed--Solomon bounded distance decoding -- from solving DLOG in $\mathbb{F}_{q^h}^\times$ to solving DLOG in finite abelian groups, and we prove that bounded distance decoding for Reed--Solomon codes is NP-hard even at asymptotically zero rate, though the known NP-hard radius lies well above the Cheng--Wan decoding radius. We then carry out Regev's reduction on the Cheng--Wan instances and evaluate it with known efficient decoders. All fall short of the Cheng--Wan threshold by a constant factor, and under an assumption on the Cheng--Wan instances we identify the QDP parameter a decoder would need to reach in order to solve discrete logarithm. The obstruction is one of efficiency rather than solvability: the Pretty Good Measurement solves the corresponding decoding problem on every instance, including NP-hard instances, but its implementation requires exponential resources in general.