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

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 2⁸⁰, 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 2^l+r+1(2l)^w ≈ 2⁷², 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.