The number of equivalent keys in multivariate cryptosystem is closely related to the scheme security. This study analyzes the structure of the private key space in some multivariate schemes. The result gives the lower...The number of equivalent keys in multivariate cryptosystem is closely related to the scheme security. This study analyzes the structure of the private key space in some multivariate schemes. The result gives the lower bounds on the number of equivalent keys of some variants of the hidden field equation (HFE) scheme including plus, minus-plus, embedding, and internal perturbation. This method estimates the number of invertible transformations which maintain the form of the central map invariant. Furthermore,a formal proof shows that the two modifications of fixing and embedding are equivalent in security analyses of multivariate schemes. Also this paper corrects previous proofs in Wolf’s work on the number of equivalent keys in HFEv,the unbalanced oil and vinegar (UOV) scheme, and the stepwise triangular systems (STS).展开更多
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 article aims at designing a new Multivariate Quadratic (MQ) public-key scheme to avoid the linearization attack and differential attack against the Matsumoto-Imai (MI) scheme. Based on the original scheme, our ne...This article aims at designing a new Multivariate Quadratic (MQ) public-key scheme to avoid the linearization attack and differential attack against the Matsumoto-Imai (MI) scheme. Based on the original scheme, our new scheme, named the Multi-layer MI (MMI) scheme, has a structure of multi-layer central map. Firstly, this article introduces the MI scheme and describes linearization attack and differential attack; then prescribes the designation of MMI in detail, and proves that MMI can resist both linearization attack and differential attack. Besides, this article also proves that MMI can resist recent eXtended Linearization (XL)-like methods. In the end, this article concludes that MMI also maintains the efficiency of MI.展开更多
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.展开更多
基金Supported by the National Key Basic Research and Development (973) Program of China (No.2007CB807902)the Tsinghua University Innovation Research Program (No.2009THZ01002)
文摘The number of equivalent keys in multivariate cryptosystem is closely related to the scheme security. This study analyzes the structure of the private key space in some multivariate schemes. The result gives the lower bounds on the number of equivalent keys of some variants of the hidden field equation (HFE) scheme including plus, minus-plus, embedding, and internal perturbation. This method estimates the number of invertible transformations which maintain the form of the central map invariant. Furthermore,a formal proof shows that the two modifications of fixing and embedding are equivalent in security analyses of multivariate schemes. Also this paper corrects previous proofs in Wolf’s work on the number of equivalent keys in HFEv,the unbalanced oil and vinegar (UOV) scheme, and the stepwise triangular systems (STS).
基金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.
基金Supported by the National High Technology Research and Development Program of China(863Program)(No.2009-aa012201)Key Library of Communication Technology(No.9140C1103040902)
文摘This article aims at designing a new Multivariate Quadratic (MQ) public-key scheme to avoid the linearization attack and differential attack against the Matsumoto-Imai (MI) scheme. Based on the original scheme, our new scheme, named the Multi-layer MI (MMI) scheme, has a structure of multi-layer central map. Firstly, this article introduces the MI scheme and describes linearization attack and differential attack; then prescribes the designation of MMI in detail, and proves that MMI can resist both linearization attack and differential attack. Besides, this article also proves that MMI can resist recent eXtended Linearization (XL)-like methods. In the end, this article concludes that MMI also maintains the efficiency of MI.
文摘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.