Improving the efficiency of Generalized Birthday Attacks against certain structured cryptosystems

Abstract : Code-based cryptographic schemes are promising candidates for post-quantum cryptography since they are fast, require only basic arithmetic, and because their security is well understood. Due to their main drawback of large public key sizes, there have been many proposals on how to reduce the key sizes. Many of these use highly structured matrices which can be stored more efficiently. In this paper, we show how a broad class of such structures can be exploited to increase the time and memory efficiency of a Generalized Birthday Attack (GBA), which is one of the best generic attacks against code-based cryptosystems. For example, this improves the best attack against QD-CFS (with n = 30924) and FSB512 by a factor of 180 and 1984, respectively. In general, for a parity-check matrix of size r*n, the improvement is a factor of r, which is typically in the order of 28 to 212.
Type de document :
Communication dans un congrès
WCC 2011 - Workshop on coding and cryptography, Apr 2011, Paris, France. pp.163-172, 2011
Liste complète des métadonnées

https://hal.inria.fr/inria-00607767
Contributeur : <>
Soumis le : lundi 11 juillet 2011 - 11:08:09
Dernière modification le : lundi 11 juillet 2011 - 11:13:48
Document(s) archivé(s) le : lundi 12 novembre 2012 - 10:41:03

Fichier

48.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00607767, version 1
  • Mot de passe :

Collections

Citation

Robert Niebuhr, Pierre-Louis Cayrel, Johannes Buchmann. Improving the efficiency of Generalized Birthday Attacks against certain structured cryptosystems. WCC 2011 - Workshop on coding and cryptography, Apr 2011, Paris, France. pp.163-172, 2011. 〈inria-00607767〉

Partager

Métriques

Consultations de la notice

260

Téléchargements de fichiers

143