We investigate the decoding problem of Reed-Solomon Codes (aka: the Polynomial Reconstruction Problem -- PR) from a cryptographic hardness perspective. First, following the standard methodology for constructing cryptographically strong primitives, we formulate a decisional intractability assumption related to the PR problem. Then, based on this assumption we show: (i) hardness of partial information extraction: an adversary who wishes to predict the value of some computable function on a new point of the solution of a given PR-instance, has no more than a negligible advantage over an adversary who wishes to do the same without seeing the PR-instance (for any probability distribution of the new point), and ii) pseudorandomness: PR-instances are pseudorandom in the sense that they are indistinguishable from totally random sets of points over the finite field.

The above results lay the theoretical framework for the exploitation of PR as a basic cryptographic tool. In fact, there are several advantages of cryptographic primitives built over this tool. For example, in PR, the size of the corrupted codeword (which corresponds to the size of a ciphertext and the plaintext) and the size of the index of error locations (which corresponds to the size of the key) are independent and can even be super-polynomially related. We know of no other problem that allows such a property. Subsequently, we present concrete constructions of primitives: First, we construct a direct one-way function that behaves as a ``large secure envelope.'' Then, we use the one-way function as a building block in a non-interactive commitment scheme for large values which is the first scheme with sublinear decommitment witness size. Further, we construct a semantically secure stateful-cipher that possesses unique properties: it allows keys to be inverse super-polynomially shorter than the encrypted messages and it satisfies ``computational perfect secrecy'', ``forward secrecy'' and ``key-equivalence.''