Welcome to the resource topic for 2005/105
Title:
On Error Correction in the Exponent
Authors: 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
- 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.
ePrint: https://eprint.iacr.org/2005/105
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .