Let X = (x_1,..,x_n) and Y = (y_1,...,y_m) be a pair of corresponding plaintext and ciphertext for a cryptosystem. We define an embedded surface of this cryptosystem as any polynomial equation:
E(X,Y)=E(x_1,..,x_n,y_1,...,y_m)=0,
which is satisfied by all such pairs. In this paper, we present a new attack on the multivariate public key cryptosystems from Diophantine equations developed by Gao and Heindl by using the embedded surfaces associated to this family of multivariate cryptosystems.