Sieve method for polynomial linear equivalence (Q1791367)

Summary: We consider the polynomial linear equivalence (PLE) problem arising from the multivariate public key cryptography, which is defined as to find an invertible linear transformation \(\mathcal L\) satisfying \(\mathcal P=\mathcal S\circ\mathcal L\) for given nonlinear polynomial maps \(\mathcal P\) and \(\mathcal S\) over a finite field \(\mathbb F_q\). Some cryptographic and algebraic properties of PLE are discussed, and from the properties we derive three sieves called multiplicative, differential, and additive sieves. By combining the three sieves, we propose a sieve method for the PLE problem. As an application of our sieve method, we show that it is infeasible to construct public key encryption schemes from the PLE problem.