The U.S. National Institute of Standards and Technology (NIST) held their Second PQC Standardization Conference at the University of California in Santa Barbara from August 22-24, 2019. Over 250 people were in attendance to review the status and hear updates on the 26 algorithms that are remaining in Round 2. These include 17 algorithms for public key encryption and key establishment algorithms and also 9 algorithms for digital signatures. As we reported on earlier, these 26 candidates remain from the original 69 candidates that were accepted at the beginning of Round 1. Some of the original candidates were withdrawn by the submitters, some schemes were merged together, some were shown to be vulnerable to attacks, some were deemed to be too inefficient and the remainder were not chosen by NIST for Round 2 due to lack of confidence in the security and other factors. NIST stated that the remaining candidates were all quite good, but also quite diverse. No single candidate currently stands out as the obvious best choice.
The 26 Round 2 candidates each have both advantages and disadvantages with regards to performance, size, maturity, flexibility and other factors. The conference included presentations by each of the submitters that provided an update of their algorithm including changes, optimizations, advantages/disadvantages, and ongoing work. Twenty-five of the 26 presentations were made in person with one additional one posted on the NIST web site along with the others for one group that wasn’t physically present.
One thing that struck us on almost all the presentations was the significant amount of continuing work that each group has been doing to improve their algorithms. Much attention was made by many of the groups to optimize either the performance and/or size of their algorithms. Significant performance measures include key generation, encapsulation, and decapsulation time as measured in CPU cycles, while size is measured by the number of bytes required for the public key, private key, and ciphertext lengths. In many cases there are tradeoffs associated with these multiple parameters so that when one parameter decreases another increases and part of the challenge is choosing the optimum balance.
Many of the groups announced that they have developed new implementations programmed in optimized C or assembly language to gain the highest efficiency. Others tweaked their algorithms or updated submodules in their code in order to improve performance. There was also significant efforts to show implementations on multiple platforms including utilization of the AVX2 (Advanced Vector Extensions) instructions available on the newer Intel and AMD microprocessors, creation of implementations for the ARM Cortex M4 processor family, and designing implementation that would fit into FPGAs like the Xilinx Artix-7 and Virtex 7 families. The ARM and FPGA implementations will be particularly important for IoT devices which we expect will represent a huge market for PQC technology in the future.
In addition, other optimizations included changes to improve the security. One concern is that some of the algorithms did not offer constant time implementations. In other words, the time it takes to complete an operation might depend upon the specific key being used or the text being encrypted or decrypted. This is not desirable because an attacker might use a side channel attack based upon these timings to break the message. Some of the algorithms do not currently provide constant time implementations and the submitters are working to update their code so that this characteristic can be included. Others submitters made changes in the parameter sets provided with their algorithms to support additional security levels as defined by NIST or to provide more flexibility for the end users to select the best tradeoffs for their particular application.
In the past, NIST has stated that it might decide to make the final selection after the completion of Round 2 or else narrow the candidate field more for a Round 3 analysis. We expect Round 2 to end sometime in early 2020 and based upon comments we heard at the conference we believe that a Round 3 is likely. There was concern from many people that additional work still needs to be performed to verify the security of many of the candidates. We also believe that that the ongoing work is continuing to make improvements in the algorithms and it would be a shame to prematurely finalize the selection before all this work has been completed.
On the other hand, people recognized that some situations may require the early implementation of a quantum resistant algorithm to protect against “Harvest Now, Decrypt Later” attack. A few folks recommended the use of a hybrid classical/quantum scheme to provide early protection for these situations. This would provide some insurance because even if an attack was discovered later for the quantum portion of the scheme, the classical encryption would still be in place. Another suggestion was to provide early approval at the end of Round 2 for one or more of the very mature coding schemes that have been around for many years. For example, the Classic McEliece cryptosystem, which was first proposed in 1978, has been studied for over 40 years with no known successful attacks. Even though its performance or key sizes may not be the best, it would represent a conservative choice for an early adopter. Additional approvals for other higher performance algorithms could then occur after the analysis is completed in Round 3. In any case, once the appropriate algorithms have been selected, NIST will draft standards and submit them for comments and approval. This process takes another 1-2 years so the estimate for final approval of the PQC standards is in the 2022 timeframe. For an overview of NIST’s Post Quantum Cryptography standardization project you can view their web page here.
On another note, we learned that the Chinese Cryptographic Society is holding their own design competition for selecting both private and public key cryptography algorithms. They recently posted 22 private key and 38 public key algorithms under consideration on the Chinese Association for Cryptologic Research (CACR) web site. The stated goal is to complete final selection by December 31, 2019. For more details you can view the competition notification here, the private key candidates here, and the public key candidates here. The web sites are in Chinese, but can be translated using Google Translate.
August 27, 2019