Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes

Aggelos Kiayias, Moti Yung

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication29th International Colloquium, ICALP 2002 Málaga, Spain, July 8--13, 2002 Proceedings
EditorsPeter Widmayer, Stephan Eidenbenz, Francisco Triguero, Rafael Morales, Ricardo Conejo, Matthew Hennessy
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages12
ISBN (Electronic)978-3-540-45465-6
ISBN (Print)978-3-540-43864-9
Publication statusPublished - 2002

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes'. Together they form a unique fingerprint.

Cite this