On Ambiguity in Coppersmith' Attacking Method a against NIKS-TAS Scheme

Shigeo TSUJII  Kiyomichi ARAKI  Masao KASAHARA  Eiji OKAMOTO  Ryuichi SAKAI  Yasuo MAEDA  Tomohiko YAGISAWA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.1   pp.66-75
Publication Date: 1996/01/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
modulo degeneracy,  cryptanalysis,  ID-based key sharing,  NIKS-TAS,  

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

In this paper it is pointed out that although an elegant differential-like approach is developed, Coppersmith' attacking method on NIKS-TAS cannot succeed to forge a shared key of legitimate entities especially when p-1 contains highly composite divisors, as well as decomposibility-hard divisors. This is mainly due to a severe reduction of modulo size. Computer simulation results confirm this assertion. The ambiguity in the solutions to the collusion equations in the first phase can be analyzed by the elementary divisor theory. Moreover, two basis vectors, qi,ri in the second phase, are found to be inadequate to represent the space spanned by xi-yi and ui-vi(i=1,...,N), because qi,ri exist frequently over the space with small modulo size. Then, the erroneous values of αii,...,εi(i=1,...,N) are derived from the inadequate basis vectors, qi,ri. Also, when the degeneracy in modulo size happens, the solutions to αii,...,εi(i=1,...,N) cannot be solved even by means of the exhaustive search over the small prime divisors of p-1.