TY - GEN
T1 - Cryptanalysis of two quartic encryption schemes and one improved MFE scheme
AU - Cao, Weiwei
AU - Nie, Xiuyun
AU - Hu, Lei
AU - Tang, Xiling
AU - Ding, Jintai
PY - 2010
Y1 - 2010
N2 - MFE, a multivariate public key encryption scheme proposed by Wang et al in CT-RSA 2006, was conquered by second order linearization equation (SOLE) attack by Ding et al in PKC 2007. To resist this attack, many improved schemes were proposed. Wang et al in [WFW09 and Wang in [Wan07] both modified MFE and raised the public key from quadratic to quartic equations. We call the two quartic schemes Quartic-1 and Quartic-2 respectively for convenience. They are indeed immune to the SOLE attack. However, we find that there exist many quadratization equations (QEs), which are quadratic in plaintext variables and linear in ciphertext variables and can be derived from the public keys of Quartic-1 and Quartic-2. In this paper, we utilize QEs to recover the corresponding plaintext for a given ciphertext. For Quartic-1, we firstly find there are at least 2r SOLEs, which was regarded as impossible by the original authors, furthermore, we can find at least 35r QEs with a complexity script O sign((90r 2(15r+1)+180r2+15r(15r+1)/2+27r+1)w), where r is a small number denoting the degree of extension of finite fields and w≈2.732. The computational complexity of deriving these equations is about 237. But to find the original plaintext, there still needs 2 40 times Gröbner basis computations, which needs practically 1.328 seconds each time. For Quartic-2, we make a theoretical analysis and find 18r QEs with a computational complexity script O sign((15r +1)6r(12r +1)+180r2 +27r +1)w. The complexity is 236 for the parameter proposed in [Wan07], and we can break the scheme practically in 3110.734 seconds. Finally, we show that another improved version of MFE in [WZY07] is insecure against the linearization equation attack although its authors claimed it is secure against high order linearization equation attack. Our attack on the two quartic schemes illustrates that non-linearization equations like quadratization equations which are not degree one in plaintext variables can also be used efficiently to analyze multivariate cryptosystems.
AB - MFE, a multivariate public key encryption scheme proposed by Wang et al in CT-RSA 2006, was conquered by second order linearization equation (SOLE) attack by Ding et al in PKC 2007. To resist this attack, many improved schemes were proposed. Wang et al in [WFW09 and Wang in [Wan07] both modified MFE and raised the public key from quadratic to quartic equations. We call the two quartic schemes Quartic-1 and Quartic-2 respectively for convenience. They are indeed immune to the SOLE attack. However, we find that there exist many quadratization equations (QEs), which are quadratic in plaintext variables and linear in ciphertext variables and can be derived from the public keys of Quartic-1 and Quartic-2. In this paper, we utilize QEs to recover the corresponding plaintext for a given ciphertext. For Quartic-1, we firstly find there are at least 2r SOLEs, which was regarded as impossible by the original authors, furthermore, we can find at least 35r QEs with a complexity script O sign((90r 2(15r+1)+180r2+15r(15r+1)/2+27r+1)w), where r is a small number denoting the degree of extension of finite fields and w≈2.732. The computational complexity of deriving these equations is about 237. But to find the original plaintext, there still needs 2 40 times Gröbner basis computations, which needs practically 1.328 seconds each time. For Quartic-2, we make a theoretical analysis and find 18r QEs with a computational complexity script O sign((15r +1)6r(12r +1)+180r2 +27r +1)w. The complexity is 236 for the parameter proposed in [Wan07], and we can break the scheme practically in 3110.734 seconds. Finally, we show that another improved version of MFE in [WZY07] is insecure against the linearization equation attack although its authors claimed it is secure against high order linearization equation attack. Our attack on the two quartic schemes illustrates that non-linearization equations like quadratization equations which are not degree one in plaintext variables can also be used efficiently to analyze multivariate cryptosystems.
KW - linearization attack
KW - multivariate public key encryption
KW - quadratic polynomial
KW - quadratization attack
KW - quartic polynomial
UR - http://www.scopus.com/inward/record.url?scp=77954392666&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-12929-2_4
DO - 10.1007/978-3-642-12929-2_4
M3 - Conference Proceeding
AN - SCOPUS:77954392666
SN - 3642129285
SN - 9783642129285
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 41
EP - 60
BT - Post-Quantum Cryptography - Third International Workshop, PQCrypto 2010, Proceedings
T2 - 3rd International Workshop on Post-Quantum Cryptography, PQCrypto 2010
Y2 - 25 May 2010 through 28 May 2010
ER -