Cryptanalysis of Double-Layer Square

摘要

Clough達［1］によって提案された多変数公開鍵（MPKC）暗号方式Squareは，Ding達［2］の発見した「同じHFE暗号でもベースとなる体の標数が大きい素数の場合は，鍵長に対する解読計算量が大きくなる」という現象に基づいた秘匿暗号方式である．この暗号が解読された後に，Clough達は［3］その解読法への対策を行った強化方式「Double-Layer Square」を発表した．本稿では，その強化方式がRank Attackによって解読可能であることを示す．%Square is one of the latest Multivariate Public Key Cryptosystem (MPKC) for encryption, proposed by Clough, et al. [1]. Its trapdoor is based on the discovery of Ding et al. [2] that the time complexity of cryptanal­ysis of the Hidden Field Encryption (HFE) increases steeply as the characteristic of the field grows. After it was attacked, Clough et al. [3] proposed to reinforce it into the "Double-Layer Square." Now we show that it is possible to eliminate the reinforcement by Rank Attack.