Single-Server Delegation of NTT with Application to Crystals-Kyber

The Number-Theory Transform (NTT) is an important operation used in many lattice-based public-key cryptosystems and, more generally, cryptographic protocols. Polynomial multiplication in quotient polynomial rings is often the most expensive computation in lattice-based public-key cryptosystems, including the current standard, Crystals-Kyber, and many other recently proposed schemes. NTT-based polynomial multiplication significantly improves runtime and yet remains the most expensive operation. Thus, optimizations and improvements are desirable, especially for implementation on resource-constrained devices.