Ciphertext-only Attack on a Multivariate Public Key Encryption Scheme with Internal Perturbation and Plus Structure  

作　　者：CAO Weiwei HU Lei 

机构地区：[1]State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, Beijing 100049, China

出　　处：《Chinese Journal of Electronics》2011年第3期511-515,共5页电子学报（英文版）

基　　金：This work is supported by the National Natural Science Foundation of China （No.61070172）, the National High Technology Research and Development Program of China （863 Program） （No.2006AA01Z416） and the National Basic Research Program of China （No.2007CB311201）.

摘　　要：This paper analyzes a new multivariate public key encryption scheme which we name as PTH＋. It is an improved version of the TH scheme by the internal perturbation and plus methods. The inventors of PTH＋ claimed that it can resist all known types of attacks including differential attack, and to ensure it achieves a security level higher than 280, they suggested its parameter is taken as （l, r, m） = （47, 6, 11）. We utilizes a distinguishing property on its differentials and combines the linearization equation attack to present a ciphertext-only attack on PTH＋ of complexity 2l＋r＋1（2l）w= 272, which is independent on the number m, and disproves a claim in their original paper that the larger is the m, the securer is PTH＋. Simulation results of small-scale parameters demonstrate our attack works.

关 键 词：Multivariate public key encryption Internal perturbation Quadratic polynomial Differential attack. 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论] TN918.2[自动化与计算机技术—计算机科学与技术]