The number of equivalent keys in multivariate cryptosystem is closely related to the scheme security. This study analyzes the structure of the private key space in some multivariate schemes. The result gives the lower bounds on the number of equivalent keys of some variants of the hidden field equation (HFE) scheme including plus, minus-plus, embedding, and internal perturbation. This method estimates the number of invertible transformations which maintain the form of the central map invariant. Furthermore, a formal proof shows that the two modifications of fixing and embedding are equivalent in security analyses of multivariate schemes. Also this paper corrects previous proofs in Wolf’s work on the number of equivalent keys in HFEv, the unbalanced oil and vinegar (UOV) scheme, and the stepwise triangular systems (STS).

ARIA is a new block cipher designed as the block cipher standard of South Korea. The current version is 1.0, which is an improvement of version 0.8 with the security using four kinds of S-boxes instead of two and an additional two rounds of encryptions. These improvements are designed to prevent the dedicated linear attack on ARIA version 0.8 by the four different kinds of S-boxes. This paper presents 12 linear approximations of a single round function that succeeds in attacking ARIA version 1.0 on 7, 9, or 9 rounds for key sizes of 128, 192, or 256 bits using any of these approximations. The corresponding data complexities are 2⁸⁷, 2¹¹⁹, and 2¹¹⁹, the counting complexities are 1.5×2⁸⁸, 2¹¹⁹, and 2¹¹⁹, the memory required for each attack on all three key versions is 2⁶⁴ bits and there are 12 weak key classes. These results are similar to the dedicated linear attack on ARIA version 0.8 and show that the improved version can also not effectively resist this type of attack.