Low-Latency Parallel Row-Layered Min-sum MDPC Decoder for McEliece Cryptosystem

In the latest round of post-quantum cryptography standardization, the McEliece cryptosystem utilizing medium-density parity-check (MDPC) codes remains a candidate. The row-layered Min-sum decoding for MDPC codes has better tradeoff between performance and complexity. Previous work adds constraints to the parity-check matrix construction in order to enable efficient parallel decoding. However, the constraints for large parallelism cause an undesirable reduction in the number of usable secret keys and hence the previous scheme has limitations in achieving higher speed. This paper proposes two new schemes to substantially reduce the latency of row-layered MDPC decoding. Instead of further increasing the constraints to achieve higher parallelism, multiple identity blocks in the parity-check matrix are processed simultaneously in the first scheme and large blocks of variable width are processed in a hybrid way in the second design. Efficient hardware architectures are also developed for both proposed decoders. For an example code, the two proposed decoders achieve around 40% speedup compared to the best prior effort with less than 10% area overhead.