A new algorithm for finding minimum-weight in large linear codes

被引：0
|
作者：
Canteaut, A
机构：
来源：
CRYPTOGRAPHY AND CODING: 5TH IMA CONFERENCE | 1995年 / 1025卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
An algorithm for finding small-weight words in large linear codes is developed and a precise analysis of its complexity is given. It is in particular able to decode random [512,256,57]-linear binary codes in 9 hours on a DEC alpha computer. We improve with it the previously best known attacks on some public-key cryptosystems and identification schemes based on error-correcting codes: for example we reduce the work factor involved in breaking McELiece's cryptosystem, since our algorithm requires 2(64) elementary operations that is 128 times less than Lee-Brickell's attack.
引用
收藏
页码：205 / 212
页数：8
相关论文
共 50 条
  • [21] A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs
    Zhang S.-Q.
    Li G.-J.
    Li S.-G.
    Acta Mathematicae Applicatae Sinica, 2004, 20 (4) : 579 - 588
  • [22] On the stabilizers of the minimum-weight codewords of some binary codes from graphs on triples
    Rodrigues, B. G.
    QUAESTIONES MATHEMATICAE, 2007, 30 (01) : 21 - 26
  • [23] Decoding Reed-Muller Codes Using Minimum-Weight Parity Checks
    Santi, Elia
    Hager, Christian
    Pfister, Henry D.
    2018 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2018, : 1296 - 1300
  • [24] Finding Minimum-Weight Link-Disjoint Paths with a Few Common Nodes
    Tao, Binglin
    Xiao, Mingyu
    Zhao, Jingyang
    THIRTY-FOURTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THE THIRTY-SECOND INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE AND THE TENTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 2020, 34 : 938 - 945
  • [25] Efficient Algorithms for Constructing Minimum-Weight Codewords in Some Extended Binary BCH Codes
    Berman, Amit
    Shany, Yaron
    Tamo, Itzhak
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2024, 70 (11) : 7673 - 7689
  • [26] Minimum-Weight Edge Discriminators in Hypergraphs
    Bhattacharya, Bhaswar B.
    Das, Sayantan
    Ganguly, Shirshendu
    ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21 (03):
  • [27] Subcodes of the projective generalized Reed-Muller codes spanned by minimum-weight vectors
    Ding, P
    Key, JD
    DESIGNS CODES AND CRYPTOGRAPHY, 2002, 26 (1-3) : 197 - 211
  • [28] Computation of Minimum Hamming Weight for Linear Codes
    Rostami, Esmaeil
    Nekooei, Reza
    IRANIAN JOURNAL OF MATHEMATICAL SCIENCES AND INFORMATICS, 2019, 14 (01): : 81 - 93
  • [29] Triangulations without minimum-weight drawing
    Wang, CA
    Chin, FY
    Yang, BT
    INFORMATION PROCESSING LETTERS, 2000, 74 (5-6) : 183 - 189
  • [30] THE MINIMUM-WEIGHT DESIGN OF STRUCTURAL FRAMES
    FOULKES, J
    PROCEEDINGS OF THE ROYAL SOCIETY OF LONDON SERIES A-MATHEMATICAL AND PHYSICAL SCIENCES, 1954, 223 (1155): : 482 - 494
12345