Hard Reliability-Based Ordered Statistic Decoding and Its Application to McEliece Public Key Cryptosystem

This letter constructs the hard reliability from the syndromes to decode low/moderate-density parity-check codes in an ordered statistic way. For regular codes with our proposed decoding algorithm, the error-correction capability can be determined by the column weight and the maximum column intersection of their parity-check matrices. Then, an upper bound is derived to verify their decoding performance in ultra-low region, which may be required by some applications, e.g., McEliece public key cryptosystem and optical communications. It allows us to reduce the size of McEliece public keys with strong security levels due to its good error-correction capability.