Advances in quantum computers pose potential threats to the currently used public-key cryptographic algorithms such as RSA and ECC.As a promising candidate against attackers equipped with quantum computational power,M...Advances in quantum computers pose potential threats to the currently used public-key cryptographic algorithms such as RSA and ECC.As a promising candidate against attackers equipped with quantum computational power,Multivariate Public-Key Cryptosystems(MPKCs)has attracted increasing attention in recently years.Unfortunately,the existing MPKCs can only be used as multivariate signature schemes,and the way to construct an efficient MPKC enabling secure encryption remains unknown.By employing the basic MQ-trapdoors,this paper proposes a novel multivariate encryption scheme by combining MPKCs and code-based public-key encryption schemes.Our new construction gives a positive response to the challenges in multivariate public key cryptography.Thorough analysis shows that our scheme is secure and efficient,and its private key size is about 10 times smaller than that of McEliece-type cryptosystems.展开更多
This paper presents a multivariate public key cryptographic scheme over a finite field with odd prime characteristic.The idea of embedding and layering is manifested in its construction.The security of the scheme is a...This paper presents a multivariate public key cryptographic scheme over a finite field with odd prime characteristic.The idea of embedding and layering is manifested in its construction.The security of the scheme is analyzed in detail,and this paper indicates that the scheme can withstand the up to date differential cryptanalysis.We give heuristic arguments to show that this scheme resists all known attacks.展开更多
During the last two decades, there has been intensive and fast development in Multivariate Public Key Cryptography （MPKC）, which is considered to be an important candidate for post-quantum cryptography. However, it ...During the last two decades, there has been intensive and fast development in Multivariate Public Key Cryptography （MPKC）, which is considered to be an important candidate for post-quantum cryptography. However, it is universally regarded as a difficult task, as in the Knapsack cryptosystems, to design a secure MPKC scheme （especially an encryption scheme） employing the existing trapdoor construction. In this paper, we propose a new key-exchange scheme and an MPKC scheme based on the Morphism of Polynomials （MP） problem. The security of the proposed schemes is provably reducible to the conjectured intractability of a new difficult problem, namely the Decisional Multivariate Diffie-Hellman （DMDH） problem derived from the MP problem. The proposed key agreement is one of several non-number-theory-based protocols, and is a candidate for use in the post-quantum era. More importantly, by slightly modifying the protocol, we offer an original approach to designing a secure MPKC scheme. Furthermore, the proposed encryption scheme achieves a good tradeoff between security and efficiency, and seems competitive with traditional MPKC schemes.展开更多
Multivariate Public Key Cryptography （MPKC） has intensively and rapidly developed during the past three decades. MPKC is a promising candidate for post-quantum cryptography. However, designing it is universally rega...Multivariate Public Key Cryptography （MPKC） has intensively and rapidly developed during the past three decades. MPKC is a promising candidate for post-quantum cryptography. However, designing it is universally regarded as a difficult task to design a secure MPKC foundation scheme, such as an encryption scheme and key exchange scheme. In this work, we investigate the security of a new public key cryptosystem that is based on the Morphism of Polynomials （MP）. The public key cryptosystem proposed by Wang et al. （Wuhan University, China） comprises a key exchange scheme and encryption scheme. Its security can be provably reduced to the hardness of solving a new difficult problem, namely, the Decisional Multivariate Diffie Hellman （DMDH） problem. This problem Js a variant of the MP problem, which is difficult to solve by random systems. We present a proposition that reduces the DMDH problem to an easy example of the MP problem. Then, we propose an efficient algorithm for the Key Recover Attack （KRA） on the schemes of the public key cryptosystem. In practice, we are able to entirely break the cryptosystem＇s claimed parameter of 96 security levels in less than 17.252 s. Furthermore, we show that finding parameters that yield a secure and practical scheme is impossible.展开更多
With the development of quantum computer, multivariate public key cryptography withstanding quantum attack has became one of the research focus. The existed signcryption schemes from discrete logarithm and bilinear pa...With the development of quantum computer, multivariate public key cryptography withstanding quantum attack has became one of the research focus. The existed signcryption schemes from discrete logarithm and bilinear paring are facing the serious threats. Based on multivariate public key cryptography, a new certificateless multi-receiver hybrid signcryption scheme has been proposed. The proposal reduced the cipher text and could handle arbitrary length messages by employing randomness reusing and hybrid encryption, as well as keeping security. In the random oracle model, the scheme＇s confidentiality could withstand the IND-CCA2 adversary and its unforgeability could withstand the UF-CMA adversary under the hardness of multivariat quadratic （MQ） problem and isomorphism of polynomials （IP） assumption. It has less computation overhead and higher transmission efficiency than others. It reduced 33% cipher data compared with the existed similar scheme.展开更多
Patarin proposed the dragon scheme, pointed out the insecurity of the dragon algorithm with one hidden monomial and suggested a candidate dragon signature algorithm with a complicated function. This paper presents an ...Patarin proposed the dragon scheme, pointed out the insecurity of the dragon algorithm with one hidden monomial and suggested a candidate dragon signature algorithm with a complicated function. This paper presents an algebraic method to attack the candidate dragon signature algorithm. The attack borrows the basic idea of the attack due to Kipnis and Shamir, and utilizes the underlying algebraic structure of the candidate dragon signature algorithm over the extension field to derive a way to enable the variable Y be viewed as a fixed value. The attack recovers the private keys efficiently when the parameters are n≤2s and D=[logq^d]≤3.展开更多
基金National Natural Science Foundation of China under Grant No. 60970115,60970116,61003267, 61003268,61003214the Major Research Plan of the National Natural Science Foundation of China under Grant No. 91018008
文摘Advances in quantum computers pose potential threats to the currently used public-key cryptographic algorithms such as RSA and ECC.As a promising candidate against attackers equipped with quantum computational power,Multivariate Public-Key Cryptosystems(MPKCs)has attracted increasing attention in recently years.Unfortunately,the existing MPKCs can only be used as multivariate signature schemes,and the way to construct an efficient MPKC enabling secure encryption remains unknown.By employing the basic MQ-trapdoors,this paper proposes a novel multivariate encryption scheme by combining MPKCs and code-based public-key encryption schemes.Our new construction gives a positive response to the challenges in multivariate public key cryptography.Thorough analysis shows that our scheme is secure and efficient,and its private key size is about 10 times smaller than that of McEliece-type cryptosystems.
基金ACKNOWLEDGEMENT This work is supported by the National Natural Science Foundation of China under Grant No.61103210, the Mathematical Tianyuan Foundation of China under Grant No.11226274, the Fundamental Research Funds for the Central Universities： DKYPO 201301, 2014 XSYJ09, YZDJ1102 and YZDJ1103, the Fund of Beijing Electronic Science and Technology Institute： 2014 TD2OHW, and the Fund of BESTI Information Security Key Laboratory： YQNJ1005.
文摘This paper presents a multivariate public key cryptographic scheme over a finite field with odd prime characteristic.The idea of embedding and layering is manifested in its construction.The security of the scheme is analyzed in detail,and this paper indicates that the scheme can withstand the up to date differential cryptanalysis.We give heuristic arguments to show that this scheme resists all known attacks.
基金supported by the National Natural Science Foundation of China (Nos.61303212,61303024,61170080,61501333,61303024,and 61332019)the Foundation of Science and Technology on Information Assurance Laboratory (No.KJ-14-002)
文摘During the last two decades, there has been intensive and fast development in Multivariate Public Key Cryptography （MPKC）, which is considered to be an important candidate for post-quantum cryptography. However, it is universally regarded as a difficult task, as in the Knapsack cryptosystems, to design a secure MPKC scheme （especially an encryption scheme） employing the existing trapdoor construction. In this paper, we propose a new key-exchange scheme and an MPKC scheme based on the Morphism of Polynomials （MP） problem. The security of the proposed schemes is provably reducible to the conjectured intractability of a new difficult problem, namely the Decisional Multivariate Diffie-Hellman （DMDH） problem derived from the MP problem. The proposed key agreement is one of several non-number-theory-based protocols, and is a candidate for use in the post-quantum era. More importantly, by slightly modifying the protocol, we offer an original approach to designing a secure MPKC scheme. Furthermore, the proposed encryption scheme achieves a good tradeoff between security and efficiency, and seems competitive with traditional MPKC schemes.
文摘Multivariate Public Key Cryptography （MPKC） has intensively and rapidly developed during the past three decades. MPKC is a promising candidate for post-quantum cryptography. However, designing it is universally regarded as a difficult task to design a secure MPKC foundation scheme, such as an encryption scheme and key exchange scheme. In this work, we investigate the security of a new public key cryptosystem that is based on the Morphism of Polynomials （MP）. The public key cryptosystem proposed by Wang et al. （Wuhan University, China） comprises a key exchange scheme and encryption scheme. Its security can be provably reduced to the hardness of solving a new difficult problem, namely, the Decisional Multivariate Diffie Hellman （DMDH） problem. This problem Js a variant of the MP problem, which is difficult to solve by random systems. We present a proposition that reduces the DMDH problem to an easy example of the MP problem. Then, we propose an efficient algorithm for the Key Recover Attack （KRA） on the schemes of the public key cryptosystem. In practice, we are able to entirely break the cryptosystem＇s claimed parameter of 96 security levels in less than 17.252 s. Furthermore, we show that finding parameters that yield a secure and practical scheme is impossible.
基金Supported by the National Natural Science Foundation of China(61103231,61103230,61272492,61202492)the Project Funded by China Postdoctoral Science Foundation and Natural Science Basic Research Plan in Shaanxi Province of China(2014JQ8358,2014JQ8307,2014JM8300)
文摘With the development of quantum computer, multivariate public key cryptography withstanding quantum attack has became one of the research focus. The existed signcryption schemes from discrete logarithm and bilinear paring are facing the serious threats. Based on multivariate public key cryptography, a new certificateless multi-receiver hybrid signcryption scheme has been proposed. The proposal reduced the cipher text and could handle arbitrary length messages by employing randomness reusing and hybrid encryption, as well as keeping security. In the random oracle model, the scheme＇s confidentiality could withstand the IND-CCA2 adversary and its unforgeability could withstand the UF-CMA adversary under the hardness of multivariat quadratic （MQ） problem and isomorphism of polynomials （IP） assumption. It has less computation overhead and higher transmission efficiency than others. It reduced 33% cipher data compared with the existed similar scheme.
基金supported by the National Natural Science Foundation of China (60970119,60803149)the Youth Science and Technology Foundation of Xi’an University of Architecture and Technology (QN0831)the National Basic Research Program of China (2007CB311201)
文摘Patarin proposed the dragon scheme, pointed out the insecurity of the dragon algorithm with one hidden monomial and suggested a candidate dragon signature algorithm with a complicated function. This paper presents an algebraic method to attack the candidate dragon signature algorithm. The attack borrows the basic idea of the attack due to Kipnis and Shamir, and utilizes the underlying algebraic structure of the candidate dragon signature algorithm over the extension field to derive a way to enable the variable Y be viewed as a fixed value. The attack recovers the private keys efficiently when the parameters are n≤2s and D=[logq^d]≤3.
