**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.

**Category / Keywords: **foundations / error correction, discrete logarithm problem, threshold cryptography

**Publication Info: **To appear in TCC 2006

**Date: **received 11 Apr 2005, last revised 8 Dec 2005

**Contact author: **cpeikert at mit edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20051209:000502 (All versions of this report)

**Short URL: **ia.cr/2005/105

[ Cryptology ePrint archive ]