Extended multivariate public key cryptosystems with secure encryption function  

作　　者：WANG HouZhen 1,2 , ZHANG HuanGuo 1,2 , WANG ZhangYi 1,2 & TANG Ming 1,2 1 The Key Laboratory of Aerospace Information Security and Trusted Computing, Ministry of Education, School of Computer, Wuhan University, Wuhan 430079, China 2 State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, China 

出　　处：《Science China(Information Sciences)》2011年第6期1161-1171,共11页中国科学（信息科学）（英文版）

基　　金：supported by the National Natural Science Foundation of China(Grant Nos.60970115,60970116,61003267,61003268,61003214);the Major Research Plan of the National Natural Science Foundation of China(Grant No.91018008)

摘　　要：Advances in quantum computers pose great threats on the currently used public key cryptographic algorithms such as RSA and ECC. As a promising candidate secure against attackers equipped with quantum computational power, multivariate public key cryptosystems （MPKCs） have attracted increasing attention in recently years. Unfortunately, the existing MPKCs can only be used as a multivariate signature scheme, and it remains unknown how to construct an efficient MPKC enabling secure encryption. Furthermore, some mul- tivariate signature schemes have been shown insecure in recent years, and it is also not trivial to build MPKC which can serve as a secure signature scheme. By employing the basic MQ-trapdoors, this paper proposes a novel MPKC and shows how it can be used as a multivariate signature scheme and a multivariate encryption scheme, respectively. The goal is achieved by incorporating our new hash authentication techniques and some modification methods such as the Shamir＇s minus method. Thorough analysis shows that our schemes are secure and efficient. Our MPKC gives a positive response to the challenges in multivariate public key cryptography.Advances in quantum computers pose great threats on the currently used public key cryptographic algorithms such as RSA and ECC. As a promising candidate secure against attackers equipped with quantum computational power, multivariate public key cryptosystems （MPKCs） have attracted increasing attention in recently years. Unfortunately, the existing MPKCs can only be used as a multivariate signature scheme, and it remains unknown how to construct an efficient MPKC enabling secure encryption. Furthermore, some mul- tivariate signature schemes have been shown insecure in recent years, and it is also not trivial to build MPKC which can serve as a secure signature scheme. By employing the basic MQ-trapdoors, this paper proposes a novel MPKC and shows how it can be used as a multivariate signature scheme and a multivariate encryption scheme, respectively. The goal is achieved by incorporating our new hash authentication techniques and some modification methods such as the Shamir＇s minus method. Thorough analysis shows that our schemes are secure and efficient. Our MPKC gives a positive response to the challenges in multivariate public key cryptography.

关 键 词：CRYPTOGRAPHY post-quantum cryptography MQ problem hash function 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]