**Cryptographic Hardness based on the Decoding of Reed-Solomon Codes**

*Aggelos Kiayias and Moti Yung*

**Abstract: **We investigate the decoding problem of Reed-Solomon (RS) Codes, also
known as the Polynomial Reconstruction Problem (PR), from a
cryptographic hardness perspective. Namely, we deal with PR instances
with parameter choices for which decoding is not known to be feasibly
solvable and where part of the solution polynomial is the hidden
input. We put forth a natural decisional intractability assumption that
relates to this decoding problem: distinguishing between a single randomly
chosen error-location and a single randomly chosen non-error location for a
given corrupted RS codeword with random noise.
We prove that under this assumption, PR-instances are entirely pseudorandom,
i.e., they are indistinguishable from random vectors over the
underlying finite field. Moreover, under the same assumption we show
that it is hard to extract any partial information related to the
hidden input encoded by the corrupted PR-instance, i.e., PR-instances
hide their message polynomial solution in the semantic security sense.

The above results lay a framework for the exploitation of PR as an intractability assumption for provable security of cryptographic primitives. Based on this framework, we present provably secure cryptographic constructions for (i) a pseudorandom extender, (ii) a semantically secure version of the Oblivious Polynomial Evaluation Protocol, and (iii) a stateful cipher with a set of interesting properties that include: semantic security, forward secrecy, error-correcting decryption and an array of random self-reducibility properties with respect to the plaintext choice, key choice and partial domain choice.

**Category / Keywords: **foundations / Coding Theory, Reed-Solomon codes

**Publication Info: **appeared in ICALP 2002 (preliminary version)

**Date: **received 25 Apr 2007

**Contact author: **aggelos at cse uconn edu

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

**Note: **This is a major revision of the original paper.

**Version: **20070426:084104 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]