Analysis and Improvement of MaTRU Public Key Cryptosystem

Jeong Eun SONG  Tae Youn HAN  Mun-Kyu LEE  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.4   pp.982-991
Publication Date: 2015/04/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.982
Type of Manuscript: PAPER
Category: Cryptography and Information Security
public key cryptography,  NTRU,  MaTRU,  polynomial ring,  

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

At Indocrypt 2005, Coglianese and Goi [1] suggested a new public key cryptosystem, MaTRU, which is a variant of NTRU. MaTRU is defined over ring M of k×k matrices whose elements are in the quotient ring R = Z[X]/(Xn-1). In addition, five example parameter sets suitable for this new structure were proposed. In this paper, we prove that it is impossible to generate appropriate key pairs for four parameter sets among the five proposed in [1] according to the key generation procedure described in [1]. The only parameter set where key pair generation is possible is when p, one of the parameters of MaTRU, is 2 and df, another parameter, is odd. Even with this parameter set, however, the decryption operation defined in [1] cannot recover an original plaintext from a given ciphertext because the value of another parameter, q, has been defined too small in [1]. Therefore, we propose an alternative method for key generation and suggest corrected parameter sets. In addition, a refined analysis for the key security of MaTRU is provided, and it is demonstrated that the key security may be significantly lower than that of the original analysis.