Content deleted Content added
Matthiaspaul (talk | contribs) m →See also: -typos |
Jsrnielsen (talk | contribs) Stub for Information Set Decoding, cut from page on McEliece |
||
Line 137:
The number of entries in the two lookup tables is <math>2^k+2^{n-k}</math>, which is significantly smaller than <math>2^n</math> required for [[standard array|standard array decoding]] that requires only <math>1</math> lookup. Additionally, the precomputed encoding lookup table can be used for the encoding, and is thus often useful to have.
== Information set decoding ==
This is a family of [[Las Vegas algorithm|Las Vegas]]-probabilistic methods all based on the observation that it is easier to guess enough error-free positions, than it is to guess all the error-positions.
The simplest form is due to Prange: Let <math>G</math> be the <math>k \times n</math> generator matrix of <math>C</math> used for encoding. Select <math>k</math> columns of <math>G</math> at random, and denote by <math>G'</math> the corresponding submatrix of <math>G</math>. With reasonable probability <math>G'</math> will have full rank, which means that if we let <math>c'</math> be the sub-vector for the corresponding positions of any codeword <math>c = mG</math> of <math>C</math> for a message <math>m</math>, we can recover <math>m</math> as <math>m = c' G'^{-1}</math>. Hence, if we were lucky that these <math>k</math> positions of the received word <math>y</math> contained no errors, and hence equalled the positions of the sent codeword, then we may decode.
If <math>t</math> errors occurred, the probability of such a fortunate selection of columns is given by <math>\textstyle\binom{n-t}{k}/\binom{n}{k}</math>.
This method has been improved in various ways, e.g. by Stern<ref>
{{cite book
| author=Jacques Stern
| year=1989
| title=A method for finding codewords of small weight
| journal=Coding Theory and Applications
| series=Lecture Notes in Computer Science
| publisher=Springer Verlag
| volume=388
| pages=106–113
| doi=10.1007/BFb0019850
| isbn=978-3-540-51643-9}}</ref> and Canteaut and Sendrier<ref>
{{cite book
| last1=Ohta
| first1=Kazuo
| last2=Pei
| first2=Dingyi
| year=1998
| editor1-last=Ohta
| editor1-first=Kazuo
| editor2-first=Dingyi
| title=Cryptanalysis of the Original McEliece Cryptosystem
| journal=Advances in Cryptology — ASIACRYPT'98
| series=Lecture Notes in Computer Science
| volume=1514
| pages=187–199
| doi=10.1007/3-540-49649-1
| editor2-last=Pei
| isbn=978-3-540-65109-3}}</ref>.
==Partial response maximum likelihood==
| |||