Post Quantum Cryptography

The consensus is 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.

FIPS 204 ML-DSA

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

A C Language implementation was coded in spare time by applying 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.

In addition, A Technical Note on Understanding FIPS 204 (ML-DSA) was shared in the NIST Post-Quantum Cryptography Community to help other practitioners.

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 by submitting 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 had to resort to the last page of my textbook on modern algebra.