The Matsumoto-Imai (MI) cryptosystem was the first multivariate public key cryptosystem proposed for practical use. Though MI is now considered insecure due to Patarin’s linearization attack, the core idea of MI has been used to construct many variants such as Sflash, which has recently been accepted for use in the New European Schemes for Signatures, Integrity, and Encryption project. Linearization attacks take advantage of the algebraic structure of MI to produce a set of equations that can be used to recover the plaintext from a given ciphertext. In our paper, we present a solution to the problem of finding the dimension of the space of linearization equations, a measure of how much work the attack will require.

We demonstrate how to prevent differential attacks on multivariate public key cryptosystems using the Plus (+) method of external perturbation. In particular, we prescribe adding as few as 10 Plus polynomials to the Perturbed Matsumoto-Imai (PMI) cryptosystem when g=1 and r=6, where θ is the Matsumoto-Imai exponent, n is the message length, g = gcd(θ,n), and r is the internal perturbation dimension; or as few as g+10 when g ≠ 1. The external perturbation does not significantly decrease the efficiency of the system, and in fact has the additional benefit of resolving the problem of finding the true plaintext among several preimages of a given ciphertext. We call this new scheme the Perturbed Matsumoto-Imai-Plus (PMI+) cryptosystem.

Sflash is a fast multivariate signature scheme. Though the first version Sflash-v1 was flawed, a second version, Sflash-v2 was selected by the Nessie Consortium and was recommended for implementation of low-end smart cards. Very recently, due to the security concern, the designer of Sflash recommended that Sflash-v2 should not be used, instead a new version Sflash-v3 is proposed, which essentially only increases the length of the signature. The Sflash family of signature schemes is a variant of the Matsumoto and Imai public key cryptosystem. The modification is through the Minus method, namely given a set of polynomial equations, one takes out a few of them to make them much more difficult to solve. In this paper, we attack the Sflash-v3 scheme by combining an idea from the relinearization method by Kipnis and Shamir, which was used to attack the Hidden Field Equation schemes, and the linearization method by Patarin. We show that the attack complexity is less than 2^{80}, the security standard required by the Nessie Consortium.

Though the multivariable cryptosystems first suggested by Matsumoto and Imai was defeated by the linearization method of Patarin due to the special properties of the Matsumoto-Imai (MI) cryptosystem, many variants and extensions of the MI system were suggested mainly by Patarin and his collaborators. In this paper, we propose a new variant of the MI system, which was inspired by the idea of “perturbation”. This method uses a set of r (a small number) linearly independent linear functions z_i=∑_{j=1}^n α_{ij}x_j + β_i, i=1,..,r, over the variables x_i , which are variables of the MI system. The perturbation is performed by adding random quadratic function of z i to the MI systems. The difference between our idea and a very similar idea of the Hidden Field Equation and Oil-Vinegar system is that our perturbation is internal, where we do not introduce any new variables, while the Hidden Field Equation and Oil-Vinegar system is an “external” perturbation of the HFE system, where a few extra (external) new variables are introduced to perform the perturbation. A practical implementation example of 136 bits, its security analysis and efficiency analysis are presented. The attack complexity of this perturbed Matsumoto-Imai cryptosystem is estimated.

The first author constructed a q-parameterized spherical category $\sC$ over C(q) in [Liu15], whose simple objects are labelled by all Young diagrams. In this paper, we compute closed-form expressions for the fusion rule of $\sC$, using Littlewood-Richardson coefficients, as well as the characters (including a generating function), using symmetric functions with infinite variables.