SHRINCS: 324-byte stateful post-quantum signatures with static backups

The discussion revolves around the security provided by 128-bit encryption, as defined within the framework of the National Institute of Standards and Technology's (NIST) evaluation criteria for post-quantum cryptography. It is pointed out that the conventional assessment, termed "64 bits against Grover's algorithm," fails to consider the significant computational demand imposed by the hash function circuit evaluation necessary for each iteration of Grover's algorithm. Specifically, the most efficient known circuit for SHA-256 processing requires a depth of $2^{14}$ gates. Furthermore, it is highlighted that Grover's algorithm exhibits poor scalability across multiple machines, with the acceleration factor being proportional to the square root of the number of machines employed. To put this into perspective, assuming quantum computing capabilities evolve to match the gate evaluation rate of contemporary laptops over a decade, deploying 268 million quantum computers to run Grover's algorithm continuously for ten years would be required under these conditions.

Additionally, the correspondence delves into the specifics of SHRINCS signature scheme at NIST security level 3, which corresponds to 192-bit classical or 96-bit quantum resistance. The details of the signature size are elaborated upon, indicating a minimum size of 660 bytes for a single query, based on certain parameters including the Winternitz parameter set to 256. This parameter setting results in the generation of 24 chains, each producing an output of 24 bytes. Alongside these outputs, the inclusion of 32-byte randomness and a 4-byte counter culminates in a total signature size of 612 bytes for the WOTS+C scheme. This meticulous breakdown underscores the nuances of post-quantum cryptographic security levels and the associated implications for signature sizes and computational demands in the context of quantum computing advancements.