Cryptanalysis of Two McEliece Cryptosystems Based on Quasi-Cyclic Codes

摘要: We cryptanalyse here two variants of the McEliece cryptosystem based on quasi-cyclic codes. Both aim at reducing key size by restricting public and secret generator matrices to be in form. The first variant considers subcodes a primitive BCH code. aforementioned constraint keys implies choose very structured permutations. prove that this is not secure producing many linear equations entries permutation matrix have satisfy using fact code subcode known This attack has been implemented all experiments we performed solution space system was dimension one revealed matrix. other uses low density parity-check (LDPC) scheme devised immune against general attacks working for type cryptosystems LDPC codes choosing more one-to-one mappings than matrices. suggest structural exploiting structure certain weakness choice transformations hide cryptanalysis adopts polynomial-oriented approach basically consists searching polynomials weight such their product polynomial. Our analysis shows with high probability punctured version can recovered time complexity O(n3) where n length considered complete reconstruction requires search codewords which done about 237 operations specific parameters proposed.