Abstract
A cryptographic compression function is the part of a hash function most responsible for compressing input while avoiding collisions. In recent years, NIST has released a Call for Proposals for a variety of cryptographic primitives, albeit there have been no calls specifically for post-quantum hash functions, as classic standards are widely considered secure against quantum threats. Nonetheless, alternative post-quantum primitives should not be disregarded in the event that novel quantum speedups are discovered. The most recent advancement in the development of lattice-based post-quantum compression functions was SWIFFT, based on the Ring Short Integer Solution (R-SIS) problem. We propose MiNTT, a family of post-quantum cryptographic compression functions based on the Module Short Integer Solution problem (M-SIS), which brings post-quantum compression up to modern standards.The hardness of M-SIS was established by Langlois and StehlΓ© via a reduction from the Module Short Independent Vectors Problem (M-SIVP), ensuring strong worst-case to average-case security guarantees. MiNTT leverages the Number Theoretic Transform to enable highly efficient polynomial multiplication. The multiplication of polynomials, which make up the key matrix and input of a MiNTT function, is the primary computational overhead of the function. We provide a range of concrete parameterizations of the MiNTT family and analyze the efficiency and security levels, including optimizations that exploit SIMD parallelism. Parameterizations are tested for concrete security as well as throughput and memory efficiency, and the top preforming variants are suggested for use in a MiNTT-based hash function.