Error Correction Laboratory

Project Summary

The fast development of quantum processors brings the imminent need of new cryptography schemes that are secure against quantum computing attacks. The code-based McEliece/Niederreiter cryptosystems, especially those based on low-density and medium-density parity check (LDPC and MDPC) error-correcting codes, are among the most promising post-quantum cryptography schemes. There has been a disconnection between the research on cryptography and error-correcting coding theory, based on which these ciphers are developed and back doors may be exposed. This proposal fills the gaps among the research on cryptography, error correcting coding theory, and hardware architecture design for the code-based McEliece/Niederreiter cryptosystems. Taking into account the specifics of the codes in the cryptosystems, new decoding algorithms and codes will be exploited to improve the resistance to existing attacks. Besides, new attacks from coding theory perspective will be investigated and countermeasures will be studied. Through cross-layer integrated algorithmic and architectural optimizations, a framework will be developed for the design and implementation of these cryptosystems achieving unprecedented small area, short latency, low power, and resistance to side-channel attacks.

Project Outline

There has been a disconnection between the research on cryptography and error-correcting coding theory, based on which these ciphers are developed and backdoors may be exposed. In particular, low-density parity-check (LDPC)
and medium-density parity-check (MDPC) error-correcting codes are the most promising codes to be used in these ciphers due to their shorter keys and high immunity to attacks compared to other codes. Compared to the simplest bit-flipping type of decoders that are used in almost every existing study, the other decoding algorithms enable better resistance to various attacks and have not been investigated. Additionally, LDPC/MDPC codes have the so called trapping sets, which are caused by certain structures in the secret-key parity check matrices of the codes. They can be revealed through decoding failures and used for key-recovery attacks. To make these code-based cryptosystems truly secure, it is essential to carry out a complete study of possible attacks from coding theory perspective and develop corresponding countermeasures.

Efficient and secure implementations are also indispensable in order to adopt a cipher in practical systems. Existing implementations of the LDPC/MDPC-based McEliece/Niederreiter cryptosystems are serial low-speed designs based on the simplest bit- flipping decoding algorithms [5, 6]. Small-area and low-latency parallel architectures for more capable decoding algorithms are needed to achieve higher level of security and broadly deploy these ciphers. The struc-ture of parity check matrices of LDPC codes used in cryptography is different from those used in digital communications: large circulant submatrices and irregularity make previous architectures ineffective and the design of small-area and high-speed parallel implementations very challenging. Additionally, even though a cipher is theoretically secure, information about the secret key may be leaked out through side-channel information, such as the timing and power consumption of the chip implementing the cipher. Hardware obfuscation/logic locking is a technique for preventing counterfeiting and protecting intellectual properties. LDPC/MDPC decoding is fault tolerant: as a result, existing hardware obfuscation schemes are not effective on the McEliece system and new methodologies need to be developed taking into account the specifics of the LDPC/MDPC decoding.

This proposal seeks to address the above mentioned challenges and develop efficient and secure hardware implementations for the code-based McEliece cryptosystems through integrating theoretical study, attack analysis, and hardware architecture design. Specifically, our proposed research proceeds along the following goals. All results can be easily extended for the Niederreiter scheme.