Linearization Equation Attack on 2-Layer Nonlinear Piece in Hand Method

Xuyun NIE  Albrecht PETZOLDT  Johannes BUCHMANN  Fagen LI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.9   pp.1952-1961
Publication Date: 2014/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.1952
Type of Manuscript: PAPER
Category: Cryptography and Information Security
multivariate cryptography,  quadratic polynomials,  algebraic cryptanalysis,  linearization equations,  piece in hand,  

Full Text: PDF(805.9KB)>>
Buy this Article

The Piece in Hand method is a security enhancement technique for Multivariate Public Key Cryptosystems (MPKCs). Since 2004, many types of this method have been proposed. In this paper, we consider the 2-layer nonlinear Piece in Hand method as proposed by Tsuji et al. in 2009. The key point of this method is to introduce an invertible quadratic polynomial map on the plaintext variables to add perturbation to the original MPKC. An additional quadratic map allows the owner of the secret key to remove this perturbation from the system. By our analysis, we find that the security of the enhanced scheme depends mainly on the structure of the quadratic polynomials of this auxiliary map. The two examples proposed by Tsuji et al. for this map can not resist the Linearization Equations attack. Given a valid ciphertext, we can easily get a public key which is equivalent to that of the underlying MPKC. If there exists an algorithm that can recover the plaintext corresponding to a valid ciphertext of the underlying MPKC, we can construct an algorithm that can recover the plaintext corresponding to a valid ciphertext of the enhanced MPKC.