Back to Search
Start Over
On the threshold of Maximum-Distance Separable codes
- Source :
- ISIT
- Publication Year :
- 2010
- Publisher :
- IEEE, 2010.
-
Abstract
- Starting from a practical use of Reed-Solomon codes in a cryptographic scheme published in Indocrypt'09, this paper deals with the threshold of linear $q$-ary error-correcting codes. The security of this scheme is based on the intractability of polynomial reconstruction when there is too much noise in the vector. Our approach switches from this paradigm to an Information Theoretical point of view: is there a class of elements that are so far away from the code that the list size is always superpolynomial? Or, dually speaking, is Maximum-Likelihood decoding almost surely impossible? We relate this issue to the decoding threshold of a code, and show that when the minimal distance of the code is high enough, the threshold effect is very sharp. In a second part, we explicit lower-bounds on the threshold of Maximum-Distance Separable codes such as Reed-Solomon codes, and compute the threshold for the toy example that motivates this study.<br />Comment: Sumitted to ISIT 2010
- Subjects :
- FOS: Computer and information sciences
Discrete mathematics
Block code
Discrete Mathematics (cs.DM)
Computer Science - Information Theory
Information Theory (cs.IT)
Concatenated error correction code
Reed–Muller code
Linear code
Code (cryptography)
Almost surely
Low-density parity-check code
Decoding methods
Computer Science - Discrete Mathematics
Computer Science::Information Theory
Mathematics
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- 2010 IEEE International Symposium on Information Theory
- Accession number :
- edsair.doi.dedup.....e1727246ccaaebdfaafc3abd67608d35