Abstract
The best known non-structural attacks against code-based cryptosystems are based on information-set decoding. Stern's algorithm and its improvements are well optimized and the complexity IS reasonably well understood. However, these algorithms only handle codes over F-2. This paper presents a generalization of Stern's information-set-decoding algorithm for decoding linear codes over arbitrary finite fields F and analyzes the complexity. This result makes it possible to compute the security of recently proposed code-based systems over non-binary fields. As an illustration, ranges of parameters for generalized McEliece cryptosysterns using classical Goppa codes over F-31 are suggested for which the new information-set-decoding algorithm needs 2(128) bit operations.
Keyword: MCELIECE CRYPTOSYSTEM,TELECOMMUNICATIONS,Stern attack,Generalized McEliece cryptosystem,information-set decoding,COMPUTER,linear codes over F-q,security analysis,ALGORITHM,LENGTH
Keyword: MCELIECE CRYPTOSYSTEM,TELECOMMUNICATIONS,Stern attack,Generalized McEliece cryptosystem,information-set decoding,COMPUTER,linear codes over F-q,security analysis,ALGORITHM,LENGTH
| Original language | English |
|---|---|
| Title of host publication | PROCEEDINGS OF POST-QUANTUM CRYPTOGRAPHY |
| Volume | Volume 6061 |
| Place of Publication | BERLIN |
| Publisher | Springer Verlag |
| Publication date | 2010 |
| Pages | 81-94 |
| ISBN (Print) | 978-36-42-12928-5 |
| Publication status | Published - 2010 |
| Externally published | Yes |
| Event | 3rd International Workshop on Post-Quantum Cryptography - Darmstadt, Germany Duration: 25 May 2010 → 28 May 2010 Conference number: 3 |
Workshop
| Workshop | 3rd International Workshop on Post-Quantum Cryptography |
|---|---|
| Number | 3 |
| Country/Territory | Germany |
| City | Darmstadt |
| Period | 25/05/2010 → 28/05/2010 |