Accelerating Multivariate Cryptography with Constructive Affine Stream Transformations

On December 20th, 2016, the National Institute of Standards and Technology (NIST) formally initiated a competition to solicit, evaluate, and standardize one or more quantum resistant cryptographic algorithms. Among the current candidates is a cryptographic primitive which has shown much promise in the post-quantum age, Multivariate Cryptography. These schemes compose two affine bijections S and T with a system of multivariate polynomials. However, this composition of S and T becomes costly as the data encrypted grows in size. Here we present Constructive Affine Stream (CAS) Transformations, a set of algorithms which enable specialized, large-scale, Aline transformations in O(n) space and O(n log n) time, without compromising security. The goal of this paper is to address the practical problems related to affine transformations common among almost all multivariate cryptographic schemes.