Typed synthesis of fast multiplication algorithms for post-quantum cryptography
Date
2024
Journal Title
Journal ISSN
Volume Title
Abstract
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.
Description
Rights Access
Subject
post quantum cryptography
ring multiplication
program synthesis
discrete Fourier transform