Let F be a finite field of q elements and P′ be a system of quadratic polynomials p1, ... , pm in n variables over F. Let S ∈ GLn(F) and T ∈ GLm(F) be linear transformations over F and P=S ˆ P′ ˆ T, where ˆ denotes the composition of functions considered here componentwise. The system P′ is called the private key and P the public key in the multivariate public key cryptoscheme.
In this note, the authors analyze that variant of multivariate PKC where P′ forms a stepwise triangular system, STS. This means that n=r1 + ... + rL and m=m1 + ... + mL with positive integers r1, ... , rL, m1, ... , mL such that p{m1+ ... + ml-1+i, 1 ≤ i ≤ ml contain only the variables xk with k ≤ &Sgr;lj=1 rj. The analysis is worked out in the special case when r1= ... =rL = m1= ... = mL=r.
There are two efficient cryptoanalytic attacks presented that break the STS-based multivariate PKC. The inversion attack recovers the message for given ciphertext in O(mn3Lqr+n2Lrqr) operations, while the structural attack computes an equivalent form of the secret key from the public key in O(mn3Lqr+mn4) steps. Both attacks are based on the observation that, for STSs, the kernels of the linear transformations associated with the matrices of the homogenous quadratic parts of the polynomials pi form a descending chain of subspaces. The proposed attacks are efficient from a theoretical point of view because the legitimate user needs O(qr) time to decrypt the message. It works well in practice too, as shown through the solution of two challenges of Kasahara and Sakai [1].
