Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes

Aggelos Kiayias; Moti Yung

doi:10.1007/3-540-45465-9_21

Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	Automata, Languages and Programming
Subtitle of host publication	29th International Colloquium, ICALP 2002 Málaga, Spain, July 8--13, 2002 Proceedings
Editors	Peter Widmayer, Stephan Eidenbenz, Francisco Triguero, Rafael Morales, Ricardo Conejo, Matthew Hennessy
Place of Publication	Berlin, Heidelberg
Publisher	Springer Berlin Heidelberg
Pages	232-243
Number of pages	12
ISBN (Electronic)	978-3-540-45465-6
ISBN (Print)	978-3-540-43864-9
DOIs	https://doi.org/10.1007/3-540-45465-9_21
Publication status	Published - 2002

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	2380
ISSN (Print)	0302-9743

Access to Document

10.1007/3-540-45465-9_21

http://link.springer.com/chapter/10.1007%2F3-540-45465-9_21

Cite this

Kiayias, A., & Yung, M. (2002). Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes. In P. Widmayer, S. Eidenbenz, F. Triguero, R. Morales, R. Conejo, & M. Hennessy (Eds.), Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8--13, 2002 Proceedings (pp. 232-243). (Lecture Notes in Computer Science; Vol. 2380). Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-45465-9_21

Kiayias, Aggelos ; Yung, Moti. / Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes. Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8--13, 2002 Proceedings. editor / Peter Widmayer ; Stephan Eidenbenz ; Francisco Triguero ; Rafael Morales ; Ricardo Conejo ; Matthew Hennessy. Berlin, Heidelberg : Springer Berlin Heidelberg, 2002. pp. 232-243 (Lecture Notes in Computer Science).

@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",

}

Kiayias, A & Yung, M 2002, Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes. in P Widmayer, S Eidenbenz, F Triguero, R Morales, R Conejo & M Hennessy (eds), Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8--13, 2002 Proceedings. Lecture Notes in Computer Science, vol. 2380, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 232-243. https://doi.org/10.1007/3-540-45465-9_21

Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes. / Kiayias, Aggelos; Yung, Moti.

Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8--13, 2002 Proceedings. ed. / Peter Widmayer; Stephan Eidenbenz; Francisco Triguero; Rafael Morales; Ricardo Conejo; Matthew Hennessy. Berlin, Heidelberg : Springer Berlin Heidelberg, 2002. p. 232-243 (Lecture Notes in Computer Science; Vol. 2380).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes

AU - Kiayias, Aggelos

AU - Yung, Moti

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

U2 - 10.1007/3-540-45465-9_21

DO - 10.1007/3-540-45465-9_21

M3 - Conference contribution

SN - 978-3-540-43864-9

T3 - Lecture Notes in Computer Science

SP - 232

EP - 243

BT - Automata, Languages and Programming

A2 - Widmayer, Peter

A2 - Eidenbenz, Stephan

A2 - Triguero, Francisco

A2 - Morales, Rafael

A2 - Conejo, Ricardo

A2 - Hennessy, Matthew

PB - Springer Berlin Heidelberg

CY - Berlin, Heidelberg

ER -

Kiayias A, Yung M. Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes. In Widmayer P, Eidenbenz S, Triguero F, Morales R, Conejo R, Hennessy M, editors, Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8--13, 2002 Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg. 2002. p. 232-243. (Lecture Notes in Computer Science). https://doi.org/10.1007/3-540-45465-9_21

Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes

Abstract

Publication series

Access to Document

Fingerprint

Cite this