Repository logo

Typed synthesis of fast multiplication algorithms for post-quantum cryptography


Multiplication over polynomial rings is a time consuming operation in many post-quantum cryptosystems. State-of-the-art implementations of multiplication for these cryptosystems have been developed by hand using an algebraic framework. A similar class of algorithms, based on the Discrete Fourier Transform, have been optimized across a variety of platforms using program synthesis. We demonstrate how the algebraic framework used to describe fast multiplication algorithms can be used in program synthesis. Specifically, we extend and then abstract this framework for use in program synthesis, allowing AI search techniques to find novel, high performance implementations of polynomial ring multiplication across platforms.


Rights Access


post quantum cryptography
ring multiplication
program synthesis
discrete Fourier transform


Associated Publications