Reducible rank codes and their applications to cryptography

We present a new family of so-called reducible rank codes which are a generalization of rank product codes . This family includes maximal rank distance (MRD) codes for lengths n>N in the field F/sub N/. We give methods for encoding and decoding reducible rank codes. A public key cryptosystem based on these codes and on the idea of a column scrambler is proposed. The column scrambler "mixes" columns of a generator (parity-check) matrix of a code. It makes the system more resistant to structural attacks such as Gibson's attacks. Possible attacks on the system are thoroughly studied. The system is found to be secure against known attacks for public keys of about 16 kbits and greater.     

New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications

We present two new algorithms for decoding an arbitrary (n, k) linear rank distance code over GF(q ^N ). These algorithms correct errors of rank r in O((Nr)³ q ^(r–1)(k+1)) and O((k + r)³ r ³ q ^{(r–1)(N–r)}) operations in GF(q) respectively. The algorithms give one of the most efficient attacks on public-key cryptosystems based on rank codes, as well as on the authentication scheme suggested by Chen.