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.展开更多
Numerous cryptographic algorithms (ElGamal, Rabin, RSA, NTRU etc) require multiple computations of modulo multiplicative inverses. This paper describes and validates a new algorithm, called the Enhanced Euclid Algorit...Numerous cryptographic algorithms (ElGamal, Rabin, RSA, NTRU etc) require multiple computations of modulo multiplicative inverses. This paper describes and validates a new algorithm, called the Enhanced Euclid Algorithm, for modular multiplicative inverse (MMI). Analysis of the proposed algorithm shows that it is more efficient than the Extended Euclid algorithm (XEA). In addition, if a MMI does not exist, then it is not necessary to use the Backtracking procedure in the proposed algorithm;this case requires fewer operations on every step (divisions, multiplications, additions, assignments and push operations on stack), than the XEA. Overall, XEA uses more multiplications, additions, assignments and twice as many variables than the proposed algorithm.展开更多
基金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.
文摘Numerous cryptographic algorithms (ElGamal, Rabin, RSA, NTRU etc) require multiple computations of modulo multiplicative inverses. This paper describes and validates a new algorithm, called the Enhanced Euclid Algorithm, for modular multiplicative inverse (MMI). Analysis of the proposed algorithm shows that it is more efficient than the Extended Euclid algorithm (XEA). In addition, if a MMI does not exist, then it is not necessary to use the Backtracking procedure in the proposed algorithm;this case requires fewer operations on every step (divisions, multiplications, additions, assignments and push operations on stack), than the XEA. Overall, XEA uses more multiplications, additions, assignments and twice as many variables than the proposed algorithm.
