Theoretical and Empirical Analysis of FALCON and SOLMAE Using Their Python Implementation

Since NIST has recently selected FALCON as one of quantum–resistant digital signatures which uses the hash-and-sign paradigm in the style of Gentry–Peikert–Vaikuntanathan framework and instantiated over NTRU lattices, SOLMAE as a variant of FALCON was submitted to KpqC competition by taking all the pros of FALCON and Mitaka and reducing their cons as much as possible. In this paper, we suggest the asymptotic computational complexity of FALCON and SOLMAE take \(\varTheta (n \log n)\) in their KeyGen, Sign and Verif procedures simultaneously, but our computer experiments using their Python implementation exhibit empirically that KeyGen of FALCON–512 takes longer time than that of SOLMAE–512 by about a second while the other two procedures are running almost the same time. We show a sample execution of FALCON–512 and SOLMAE–512 with their real value are described in detail for the educational purpose to understand FALCON and SOLMAE easily. We also checked the Gaussian randomness of \(\mathcal N\) -Sampler and UnifCrown samplers used in SOLMAE only.