Clarifying the specification of linear Piece In Hand matrix method

The linear Piece In Hand (PH, for short) matrix method with random variables was proposed in our previous work [S. Tsujii, K. Tadaki, and R. Fujita, IEICE Transactions on Fundamentals, E90-A, No.5, pp.992-999, 2007]. It is a general prescription which can be applicable to any type of multivariate public key cryptosystems for the purpose of enhancing their security. Actually, we showed, in an experimental manner, that the linear PH matrix method with random variables can certainly enhance the security of HFE against the Gröbner basis attack, where HFE is one of the major variants of multivariate public key cryptosystems. In the linear PH matrix method with random variables, the three secret matrices: the PH matrix M, S and R play a central role in the key-generation. In our former work [K. Tadaki and S. Tsujii, IEICE Transactions on Fundamentals, E93-A, No.6, pp.1102-1110, 2010], we presented a key-generation algorithm which generates these matrices. In this paper, we make more clear the specification of the linear PH matrix method with random variables. In the linear PH matrix method, a matrix A is introduced to the public key of the enhanced multivariate public key cryptosystem internally in order to prevent an eavesdropper from forging the PH matrix. In this paper, we first investigate a necessary condition for the matrix A to satisfy by considering the immunity against a variant of the attack by Courtois, Daum, and Felke against HFEv-, on which the signature scheme Quartz is based. Based on this investigation, we then present a complete and concise key-generation algorithm for the linear PH matrix method with random variables, which generates the complete secret key (M; S; R; A) of the method.