Three Bears is a KEM whose security is based on the presumed hardness of the Integer Module Learning With Errors (I-MLWE) problem, a new variant of the MLWE problem. It draws its inspiration from and, more explicitly, from KYBER and related improvements to the MLWE-like design paradigm that have been devised over time. Three Bears is one of two examples of candidates that are a non-cyclotomic structured lattice KEM. The chosen polynomial ring underlying the module structure in Three Bears is isomorphic to the integers modulo a generalized Mersenne prime, and elements of the ring are written simply as (large) integers in the provided implementations. The scheme also uses an internal Melas forward error correcting code in all parameter sets. Altogether, this leads to a highly efficient scheme. In the second round, the security proof sketch in the submission documentation was updated to a formal proof. In addition, parameters were slightly modified to lower the decryption failure rate, along with a detailed analysis for bounding the rate. A later tweak during the second round made implicit rejection mandatory in the specification. Noting there is a security reduction which shows the asymptotic security equivalence of the usual notion of RLWE and Integer-RLWE, and this proof appears to carry directly over to the case of MLWE and I-MLWE. However, the I-MLWE hardness assumption was essentially created for the sake of submission to the PQC standards process and has not undergone enough rigorous review by the broader cryptographic research community. While the reduction exists between I-MLWE and MLWE, there is still the possibility of concrete attacks exploiting the I-MLWE structure that are not fully captured by the security reduction, or other new issues that may have not been discovered yet. In a similar vein, it seems that the entire Three Bears submission package appears to have received less attention by third-party researchers than other KEM submissions, particularly other lattice KEM submissions. While I believe the technical and scientific merits of Three Bears are significant, this is not a substitute for a sufficient threshold of broader community attention. We therefore choose not to keep Three Bears under consideration, as there are other options which have comparable security and performance
CRYSTALS-DILITHIUM was one of three lattice-based signature schemes in the second round. The security of DILITHIUM relies on the hardness of the MLWE and module short integer solutions problems (MSIS) and follows the Fiat-Shamir with aborts technique. DILITHIUM uses the same modulus and ring for all parameter sets and samples via the uniform distribution, which results in a simpler implementation than its main competitor, FALCON. Overall, DILITHIUM has strong, balanced performance in terms of key and signature sizes and in the efficiency of the key generation, signing, and verification algorithms. DILITHIUM performs well in real-world experiments. For the second round, DILITHIUM added the option to generate a signature nondeterministically and added an implementation based on using AES rather than SHAKE to illustrate the future benefits of hardware instructions. In addition, new research on security in the QROM was published, which applies to DILITHIUM.
We have selected DILITHIUM as a finalist and expect that either DILITHIUM or FALCON will be standardized as the primary post-quantum signature scheme at the conclusion of the third round.
FALCON is a lattice-based signature scheme utilizing the “hash and sign” paradigm. Security is based on the hardness of the SIS (short integer solution) problem over NTRU lattices, and security proofs are given in both the random oracle model (ROM) and QROM with tight reductions. FALCON is more complex to implement than DILITHIUM, requiring tree data structures, extensive floating-point operations, and random sampling from several discrete Gaussian distributions. One of the advantages of FALCON is that it offers the smallest bandwidth (public key size and signature size) of all of the second-round digital signature schemes. FALCON is also efficient in signing and verifying, although key generation is slower. FALCON can easily be put into existing protocols and applications and offers very good overall performance.
At the beginning of the second round, FALCON removed their category 3 parameter sets, which simplified their specification and implementation because they used a different modulus and ring choice. The other major update during the second round was a constant-time implementation released shortly after NIST’s 2nd PQC Standardization Conference.
During the third round, we encourage more scrutiny of FALCON’s implementation to determine whether the use of floating-point arithmetic makes implementation errors more likely than other schemes or provides an avenue for side-channel attacks. In addition, it would be helpful to have test vectors for the sampler, perhaps by making it deterministic for a random seed, so that implementations can be verified using known answer tests (KATs). As with several other candidates, FALCON’s category 1 parameters have relatively low CoreSVP security strength, and so further study is needed.
FALCON was selected as a third-round finalist. As stated above, we expect that either DILITHIUM or FALCON will be standardized as the primary post-quantum signature scheme at the conclusion of the third round.
GeMSS is a multivariate signature scheme constructed using the “big field” paradigm. GeMSS is based on the HFEv- construction originating in the late 1990s. The scheme utilizes a Fiestel-Patarin construction to bootstrap EUF-CMA security from the assumed universal unforgeability of the HFEv- primitive.
GeMSS offers the smallest signatures of any digital signature candidate, supports a reasonably fast verification algorithm, and rests on a stable and well-studied mathematical problem. The drawbacks of the scheme include extremely large public keys, difficulty implementing the algorithm on low-end devices, and signing times ranging from slow to very slow. With these performance security characteristics, GeMSS seems to be a good and appropriate tool for applications in which offline signing and no transmission of the public key are acceptable and expected. GeMSS’s large public keys may not work in many implementations of TLS and SSH without some implementation updates. The second-round inclusion of the RedGeMSS and BlueGeMSS parameter sets offers additional flexibility in the performance properties over the initial submission package and appropriately addresses the concerns raised. It is possible that there may yet be additional trade-offs to further improve performance. In particular, the consideration of the number of bit operations involved in a hash collision attack may warrant a reevaluation of the number of iterations required in the Fiestel-Patarin transformation. As with Rainbow, ROLLO, and RQC, the complexity of some key recovery attacks against GeMSS was affected by recent progress on algebraic methods for solving MinRank. However, this research did not contradict the claimed security of any of GeMSS’s proposed parameter sets. GeMSS competes most closely with Rainbow, another multivariate signature scheme with large keys and small signatures. GeMSS has much bigger public keys and much slower signing in exchange for slightly smaller signatures; Rainbow’s performance profile is more appealing for most applications, and GeMSS appears to be difficult to implement on low-end devices. GeMSS is also based on a different security assumption. We see GeMSS as an option for standardization if developments during the third round show Rainbow to be unacceptable for standardization. For these reasons, GeMSS was chosen as an alternative candidate.