Paper 2023/733

On implemented graph based generator of cryptographically strong pseudorandom sequences of multivariate nature

Abstract

Classical Multivariate Cryptography (MP) is searching for special families of functions of kind ^nF=T_1FTT_2 on the vector space V= (F_q)^n where F is a quadratic or cubical polynomial map of the space to itself, T_1 and T^2 are affine transformations and T is the piece of information such that the knowledge of the triple T_1, T_2, T allows the computation of reimage x of given nF(x) in polynomial time O(n^ᾳ). Traditionally F is given by the list of coefficients C(^nF) of its monomial terms ordered lexicographically. We consider the Inverse Problem of MP of finding T_1, T_2, T for F given in its standard form. The solution of inverse problem is harder than finding the procedure to compute the reimage of ^nF in time O(n^ᾳ). For general quadratic or cubic maps nF this is NP hard problem. In the case of special family some arguments on its inclusion to class NP has to be given.