@inproceedings{75c4a3a507304c4f9f684da84e849cf1,
title = "Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes",
abstract = "We investigate the decoding problem of Reed-Solomon Codes (aka: the Polynomial Reconstruction Problem - PR) from a cryptographic hardness perspective. 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 and (ii) pseudorandomness. This lays the theoretical framework for the exploitation of PR as a basic cryptographic tool which, as it turns out, possesses unique properties. One such property is the fact that 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 then demonstrate the power of PR-based cryptographic design by constructing a stateful cipher.",
author = "Aggelos Kiayias and Moti Yung",
year = "2002",
doi = "10.1007/3-540-45465-9_21",
language = "English",
isbn = "978-3-540-43864-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer Berlin Heidelberg",
pages = "232--243",
editor = "Peter Widmayer and Stephan Eidenbenz and Francisco Triguero and Rafael Morales and Ricardo Conejo and Matthew Hennessy",
booktitle = "Automata, Languages and Programming",
}