Abstract:

The multivariate public key cryptosystem has the problem that multiple private keys correspond

 to a common public key. This paper defines the Plus sustaining transformation and presents 

its expression. The problem of equivalent keys in some multivariate public key cryptographic 

schemes is investigated with the Plus sustaining transformation and other sustaining trans-

formations. It is proved that the equivalent-keys of the Square scheme can be obtained 

only through the Big and the Frobenius sustaining transformation. The results show that the 

private key space can be significantly reduced due to the fact that any given public key 

corresponds to exponentially many private keys. Accordingly, to achieve the expected 

security, we must choose larger system parameters in the multivariate public key cryptosystems.

 Moreover, by utilizing the sparse normal form of affine transformations of private keys, we can 

effectively reduce the computational complexity and the storage requirements. 

Key words: cryptography, public key cryptography, polynomials, mapping, equivalence classes, multivariate, sustaining transformations