Post Quantum Cryptography

The consensus appears that quantum computers will be built, and RSA and ECC will be broken by Shor's algorithm at some point. Although scepticism on quantum computing exists (see Some critical publications on Quantum Computing), the possibility cannot be ignored. As a result, NIST formally issued a "Call for Proposals" for post-quantum cryptographic algorithms on December 20, 2016. and submissions for the first round were then due by November 30, 2017, and 69 complete and proper submissions were announced as first-round candidates on December 21, 2017.

SIKE

Around 2020, hopefuls were clear. Among of them, SIKE (Supersingular Isogeny Key Exchange) looked a very good candidate for its small key size and small ciphertext size. In 2021, I coded SIKE in my spare time. During the coding, I found the SIKE specification's algorithm for computing and evaluating a isogeny was quite complicated. However, if this algorithm coded recursively, the recursion not only made the code simple, but also made the concept of isogeny evaluation easy to understand.

I summarised my work and submitted a paper to PQC'2022 conference (see A Divide-and-Conquer Implementation of SIDH and its Relative Performance), hoping to share the experience and with relative performance figures to justify the viability of SIKE - the point was that, although SIKE was not as fast as other PQC candidates, its performance was comparable with the current standardised Diffie-Hellman system. Unfortunately, the paper was rejected with the reason of lack of innovation and the implementation's performance in terms of absolute performance. (BTW, I was a performance benchmark expert when I worked in Freescale (formerly Motorola Semiconductors) to benchmark their high-performance PowerPC products for EEMBC.)

I read through the feedback from the reviewers and realised the discrepancy. I planned to update this paper for other conferences. Considering some same reviewers could review the updated paper again, I prepared my comments as Comments on PQC2022 Rejection to explain the purpose of the paper. However, SIKE was broken just before NIST's Round 4 Submissions (see NIST Post-Quantum Cryptography Candidate Cracked). The effort for further work on SIKE stopped.

Unexpectedly, SIKE was broken by a method existed since 1997. This shows the the rarity of deep understanding on isogeny and the lack of experts in this difficult mathematics area. On a positive side, this effort has further extended my expertise in modern algebra - I resorted to the last page of my textbook on modern algebra.

FIPS 204 (ML-DSA) / CRYSTAL-Dilithium

After CRYSTAL-Kyber and CRYSTAL-Dilithium were standardised as FIPS 203 (ML-KEM) and FIPS 204 (ML-DSA) respectively, the focus was turned to lattice-based post quantum cryptography. FIPS 204 (ML-DSA) was coded to have a better understanding the FIPS 204 specification and to have a platform for further optimisation.

It is a full C Language implementation coded in spare time applied Montgomery arithmetic to NTT innovatively (see Applying Montgomery Multiplication to Implementing FIPS204 (ML-DSA) and here). A worked example, An FIPS204_ML-DSA-44 Worked Example (and here) is available for those who would like to cross check their implementations.