Search

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, affine 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.

Certain families of graphs can be used to obtain multivariate polynomials for cryptographic algorithms. In particular, in this paper, we introduce stream ciphers based on non-bijective multivariate maps. The presented symmetric encryption algorithms are based on three families of bipartite graphs with partition sets isomorphic to $\mathbb{K}^{n}$ where $\mathbb{K}$ is selected as the finite commutative ring. The plainspace of the algorithm is $\Omega = \{x\vert \sum x_{i} \in \mathbb{K}{\ast},x \in \mathbb{K}^{n}\} \subset \mathbb{K}^{n}, \Omega\cong \mathbb{K}{\ast} \times \mathbb{K}^{n-1}$ . We describe the algorithm for the case $\mathbb{K}= \mathbb{Z}_{2^{m}}, m \leq 2$ . In fact, we use the relation $d \ast d_{dec}\equiv 1(\mod 2^{m-1}), d, d_{dec}\in\mathbb{Z}^{\ast}_{2^{m-1}}$ to obtain encryption polynomial map of degree greater than or equal to $d + 2$ and decryption map of degree greater than or equal to $d_{dec} + 2$ . We assume $d_{dec}$ grows with the growth of parameter $m$ , because this makes cryptanalysis very difficult task. Symmetric encryption and decryption algorithms for users are numerical recurrent processes, not requiring generation of encryption and decryption maps in their symbolic forms. They use arithmetical operations of addition, subtraction, and multiplication. That's why the algorithms are robust (execution speed is $O(n)$ ). To break the algorithm an adversary must use linearization attacks for recovering non-bijective “decryption map” of degree greater than $d_{dec} + 2$ in its symbolic form. To achieve this, the adversary needs at least $O(n d_{dec} + 2)$ pairs of plaintext and corresponding ciphertext to restore the non-bijective map of degree greater than or equal to $d_{dec} + 2$ . We present tables for evaluation of execution time for m = 8 with various length of passwords and sizes of files. Computer simulations demonstrate good mixing properties of the encryption functions.