In this paper we propose a new multivariate public key encryption scheme named ZHFE. The public key is constructed using as core map two high rank HFE polynomials. The inversion of the public key is performed using a low degree polynomial of Hamming weight three. This low degree polynomial is obtained from the two high rank HFE polynomials, by means of a special reduction method that uses Hamming weight three polynomials produced from the two high rank HFE polynomials. We show that ZHFE is relatively efficient and that it is secure against the main attacks that have threatened the security of HFE. We also propose parameters for a practical implementation of ZHFE.

In this paper, we try to clarify some of the questions related to a key concept in multivariate polynomial solving algorithm over a finite field: the degree of regularity. By the degree of regularity, here we refer to a concept first presented by Dubois and Gama, namely the lowest degree at which certain nontrivial degree drop of a polynomial system occurs. Currently, it is somehow commonly accepted that we can use this degree to estimate the complexity of solving a polynomial system, even though we do not have systematic empirical data or a theory to support such a claim. In this paper, we would like to clarify the situation with the help of experiments. We first define a concept of solving degree for a polynomial system. The key question we then need to clarify is the connection of solving degree and the degree of regularity with focus on quadratic systems. To exclude the cases that do not represent the general situation, we need to define when a system is degenerate and when it is irreducible. With extensive computer experiments, we show that the two concepts, the degree of regularity and the solving degree, are related for irreducible systems in the sense that the difference between the two degrees is indeed small, less than 3. But due to the limitation of our experiments, we speculate that this may not be the case for high degree cases.

Multivariate public key cryptosystems are being focused on as candidates for post-quantum cryptography. Rainbow is one of the most efficient signature schemes in multivariate public key cryptosystems. The main drawback of Rainbow is that their key size is much larger than that of RSA and ECC. In this paper, we propose an efficient variant of Rainbow that has a shorter secret key (and thus generates signatures faster) than the corresponding original Rainbow. In our scheme, we divide each layer of Rainbow into smaller blocks by using diagonal matrix representations. The size of the smaller blocks can be flexibly selected, and this enables us to carefully choose secure parameters so that our proposed scheme is secure against known attacks such as rank attacks, direct attacks, and UOV attack. We estimate that the secret key size of our proposed scheme with 100-bit security is smaller by about 40% than that of the original Rainbow. In addition, an implementation of our scheme in the C language is seen to generate signature faster by 40%.

MIFARE Classic is the world’s most widely deployed RFID (radio-frequency identification) technology. It was claimed to be cryptographically protected by the proprietary Crypto-1 stream cipher. However, it proved inadequate after weaknesses in the design and implementation of Crypto-1 and MIFARE Classic started surfacing since late 2007 [7, 8, 12–17]. Some operators of MIFARE Classic-based systems reacted by upgrading to more secure alternatives such as MIFARE DESFire. However, many (especially in Asia) opted to “patch” MIFARE Classic instead. Their risk analysis might have gone as follows: “The most serious threat comes from efficient card-only attacks, where the attacker only needs an off-the-shelf reader and a PC to tamper a target tag. All efficient card-only attacks depend on certain implementation flaws. Ergo, if we just fix these flaws, we can stop the most serious attacks without an expensive infrastructure upgrade.” One such prominent case is “EasyCard 2.0,” today accepted in Taiwan as a means of electronic payment not only in public transportation but also in convenient stores, drug stores, eateries, cafes, supermarkets, book stores, movie theaters, etc. Obviously, the whole “patching” approach is questionable because Crypto-1 is fundamentally a weak cipher. In support of the proposition, we present a new card-only attack based on state-of-the-art algebraic differential cryptanalytic techniques [1, 2]. Still using the same cheap reader as previous attacks, it takes 2–15 min of computation on a PC to recover a secret key of EasyCard 2.0 after 10–20 h of data collection. We hope the new attack makes our point sufficiently clear, and we urge that all MIFARE-Classic operators with important transactions such as electronic payment upgrade their systems to the more secure alternatives soon.

In this paper, we first prove an explicit formula which bounds the degree of regularity of the family of HFEv (“HFE with vinegar”) and HFEv- (“HFE with vinegar and minus”) multivariate public key cryptosystems over a finite field of size q. The degree of regularity of the polynomial system derived from an HFEv- system is less than or equal to \frac{(q−1)(r+v+a−1)}{2}+2 if q is even and r+a is odd, \frac{(q−1)(r+v+a−1)}{2}+2 otherwise, where the parameters v, D, q, and a are parameters of the cryptosystem denoting respectively the number of vinegar variables, the degree of the HFE polynomial, the base field size, and the number of removed equations, and r is the “rank” paramter which in the general case is determined by D and q as r=⌊log_q (D−1)⌋+1. In particular, setting a = 0 gives us the case of HFEv where the degree of regularity is bound by \frac{(q−1)(r+v−1)}{2}+2 if q is even and r is odd, \frac{(q−1)(r+v)}{2}+2 otherwise. This formula provides the first solid theoretical estimate of the complexity of algebraic cryptanalysis of the HFEv- signature scheme, and as a corollary bounds on the complexity of a direct attack against the QUARTZ digital signature scheme. Based on some experimental evidence, we evaluate the complexity of solving QUARTZ directly using F_4/F_5 or similar Gröbner methods to be around 2^{92}.