## 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 | International Workshop on Post-Quantum Cryptography - Duration: 1 Jan 2010 → … Conference number: 3 |

### Conference

Conference | International Workshop on Post-Quantum Cryptography |
---|---|

Number | 3 |

Period | 01/01/2010 → … |