I regard my work on hash-based digital signatures as the most important outcome of my doctoral research. It was published at CRYPTO 2023, and the resulting scheme was also submitted to NIST. I believe it is a strong candidate for a Chinese cryptographic standard. Unfortunately, the Institute of Commercial Cryptography Standards (ICCS) rejected my hash-based signature submission to the Next-generation Commercial Cryptographic Algorithms Program (NGCC) at the preliminary compliance review stage. The main reason given was that its quantum security fell short of 80 bits.
ICCS informed me of the decision in advance by telephone, and I expressed my objection. I acknowledge that there was an oversight on my part. At the same time, I believe ICCS showed a considerable lack of experience in both formulating and applying the rules. Here are the details.
First, when I prepared the submission, hash-based digital signatures were no longer my main research focus. I considered the field relatively mature, and I expected that adapting my existing NIST submission with minor revisions would be straightforward. I had noticed that NGCC requires 128 bits of classical security and 80 bits of quantum security at its lowest security level. This pairing does not follow the usual Grover-based rule of thumb of halving the classical security level in bits, whereas the higher-level pairings of 256/128 and 512/256 bits do.
The technical issue, however, is more subtle. For the hash-based signature scheme at issue, a key bottleneck in the security estimate is a probabilistic collision event: multiple signatures happen to select the same leaf, potentially making a forgery possible. Writing the relevant probability as p, we express the corresponding classical security estimate as
secclassic = −log2 p.
For quantum security, to my knowledge, no application of Grover's algorithm is known to achieve the assumed quadratic speedup for this particular collision event. In this context, setting
secquantum = ½ secclassic
is a conservative estimate. It does not establish a concrete quantum attack that achieves that cost. NIST's Category 1 benchmark is security comparable to AES-128, and NIST accepted our submission, with its security estimates, into its evaluation process.
Second, combining an 80-bit quantum-security requirement with the Grover-based halving rule effectively requires 160 bits of classical security for schemes assessed in this way. This puts those Chinese candidates at an efficiency disadvantage compared with schemes targeting 128-bit classical security in the NIST process. I do not see how following this rule will help Chinese cryptographic algorithms gain international adoption and become standards for communications around the world. If this approach continues, I expect their use to remain largely confined to meeting government or industry compliance requirements.
Finally, the rapid progress of artificial intelligence in mathematics and computer science points toward a future in which both the design of cryptographic algorithms and the analysis of their security can be fully automated. In my view, AI is the more consequential development of our time. It deserves greater attention than preparing for cryptographically relevant quantum computers whose arrival remains uncertain.
I will leave it at that for now.
Kaiyi Zhang