Cryptanalysis of novel extended multivariate public key cryptosystem

Xu-yun NIE; Bo LIU; Gang LU; Ting ZHONG

doi:10.11959/j.issn.1000-436x.2015182

您当前的位置：

首页 >

文章列表页 >

Cryptanalysis of novel extended multivariate public key cryptosystem

Academic paper | 更新时间：2024-06-05

- Cryptanalysis of novel extended multivariate public key cryptosystem
- Journal on Communications Vol. 36, Issue 6, Pages: 60-65(2015)
- 作者机构：
  
  1. 电子科技大学信息与软件工程学院，四川成都 611731
  2. 中国科学院信息工程研究所信息安全国家重点实验室，北京 100093
  3. 电子科技大学计算机科学与工程学院，四川成都 611731
- 作者简介：
- 基金信息：
  
  The National Natural Basic Research Program of China(2013CB834203);The National Natural Science Foundation of China(61370026);The National Natural Science Foundation of China(61472064)
- DOI：10.11959/j.issn.1000-436x.2015182
  CLC： TN918.1
- Online First：2015-06，
  
  Published：25 June 2015
- 稿件说明：
移动端阅览
Xu-yun NIE, Bo LIU, Gang LU, et al. Cryptanalysis of novel extended multivariate public key cryptosystem[J]. Journal on Communications, 2015, 36(6): 60-65.
DOI：

Xu-yun NIE, Bo LIU, Gang LU, et al. Cryptanalysis of novel extended multivariate public key cryptosystem[J]. Journal on Communications, 2015, 36(6): 60-65. DOI： 10.11959/j.issn.1000-436x.2015182.

摘要

新扩展多变量公钥密码方案是乔等提出的一种多变量公钥密码体制的安全性增强方案。该方案引入了一个非线性“温顺变换”，试图隐藏原始方案的弱点，如线性化方程。然而，分析表明，若原始方案满足线性化方程，则改进方案必然满足二次化方程。给定公钥，在找到所有的二次化方程之后，将要破解的合法密文代入到二次化方程中，可以得到关于明文变量的二次方程。这降低了要求解的方程组的次数。结合Groebner基方法，可以快速地恢复合法密文相应的明文。

Abstract

The novel extended multivariate public key cryptosystem is a new security enhancement method on multivariate public key cryptosystems

which is proposed by Qiao

et al.A nonlinear invertible transformation was used

named“tame transformation”

on the original multivariate public key cryptosystem to hide its weakness such as linearization equation.However

it is found that if there are many linearization equations satisfied by the original MPKC

there would be many quadratization equations (QE) satisfied by the improved scheme.Given a public key

after finding all QE

a valid cipheretext can be substituted into the QE to derive a set of quadratic equations on the plaintext variable.This exactly reduce the degree of the system wanted to solve.Then the corresponding plaintext can be recovered for a given valid ciphertext combining with Groebner basis method.

关键词

Keywords

references

DING J T , GOWER J , SCHMIDT D . Multivariate Public Key Cryptosystems [M ] . Berlin : Springer-VerlagPress , 2006 .

PATARIN J . Cryptanalysis of the Matsumoto and Imai public key scheme of eurocrypt 1988 [A ] . Proceedings of Advances in Cryptology,Crypto 1995 [C ] . Santa Barbara,California,USA , 1995 . 248 - 261 .

MATSUMOTO T , IMAI H . Public quadratic polynomial-tuples for efficient signature verification and message encryption [A ] . Proceedings of Advances in Cryptology- Eurocrypt’88 [C ] . Davos,Switzerland , 1988 . 419 - 453 .

DING J T,HU L , NIE X Y , LI J Y,WAGNERJ . High order linearization equation (HOLE) attack on multivariate public key cryptosystems [A ] . Proceedings of Public key Cryptography-PKC 2007 [C ] . Beijing,China , 2007 . 233 - 248 .

WANG L C,YANG B Y , HU Y H , LAI F . A medium-field multivariate public-key encryption scheme [A ] . Proceedings of Topics in Cryptology,CT-RSA 2006 [C ] . San Jose,CA,USA , 2006 . 132 - 149 .

WANG X,FENG F , WANG X , WANG Q . A more secure MFE multivariate public key encryption scheme [J ] . International Journal of Computer Science and Applications , 2009 , 6 ( 3 ): 1 - 9 .

CAO W W,NIE X Y,HU L , TANG X L , DING J T . Cryptanalysis of two quartic encryption schemes and one improved MFE scheme [A ] . Proceedings of Cryptology,PQCrypto 2010 [C ] . Darmstadt,Germany , 2010 . 41 - 60 .

乔帅庭 , 李益发 , 韩文报 . 新扩展多变量公钥密码方案 [J ] . 通信学报 , 2014 , 35 ( 4 ): 148 - 154 .

QIAO S T , LI Y F , HAN W B . Novel extended multivariate public key cryptosystem [J ] . Journal on Communications , 2014 , 35 ( 4 ): 148 - 154 .

NIE X Y,PETZOLDT A , BUCHMANN J , LI F G . Linearization equation attack on 2-layer nonlinear piece in hand method [J ] . IEICE Transactions , 2014 , 97 ( 9 ): 1952 - 1961 .

DIENE A,DING J T,GOWER J E , HODGES T J , YIN Z J . Dimension of the linearization equations of the Matsumoto-Imai cryptosystems [A ] . Proceedings of Code and Cryptography—WCC 2005 [C ] . Bergen,Norway , 2005 . 242 - 251 .

Views

885

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Novel extended multivariate public key cryptosystem

Algebraic fault attack on PRESENT

Related Author

Shuai-ting QIAO

Yi-fa LI

Wen-bao HAN

Ke-hui WU

Xin-jie ZHAO

Tao WANG

Shi-ze GUO

Hui-ying LIU

Related Institution

The Fourth Institute Information Engineering University

State Key Laboratory of Mathematical Engineering and Advanced Computing

Department of Computer Engineering,Ordnance Engineering College

The Institute of North Electronic Equipment

AI问答

⁰