Paper 2005/105

On Error Correction in the Exponent

Chris Peikert

Abstract

Given a corrupted word $\w = (w_1, \ldots, w_n)$ from a Reed-Solomon code of distance $d$, there are many ways to efficiently find and correct its errors. But what if we are instead given $(g^{w_1}, \ldots, g^{w_n})$ where $g$ generates some large cyclic group --- can the errors still be corrected efficiently? This problem is called \emph{error correction in the exponent}, and though it arises naturally in many areas of cryptography, it has received little attention. We first show that \emph{unique decoding} and \emph{list decoding} in the exponent are no harder than the computational Diffie-Hellman (CDH) problem in the same group. The remainder of our results are negative: * Under mild assumptions on the parameters, we show that \emph{bounded-distance decoding} in the exponent, under $e=d-k^{1-\epsilon}$ errors for any $\epsilon > 0$, is as hard as the discrete logarithm problem in the same group. * For \emph{generic} algorithms (as defined by Shoup, Eurocrypt 1997) that treat the group as a ``black-box,'' we show lower bounds for decoding that exactly match known algorithms. Our generic lower bounds also extend to decisional variants of the decoding problem, and to groups in which the decisional Diffie-Hellman (DDH) problem is easy. This suggests that hardness of decoding in the exponent is a qualitatively new assumption that lies ``between'' the DDH and CDH assumptions.