On Ambiguity in Coppersmith' Attacking Method against NIKS-TAS Scheme (Special Section on Cryptgraphy and Information Security)

概要

論文の詳細を見る
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 dolutions to the collusion equations in the first phase can be analyzed by the elementary divisor theory. Moreover, two basis vectors, q_i, r_i in the second phase, are found to be inadequate to represent the space spanned by x_i-y_i and u_i-v_i (i=1,..., N), because q_i,r_i exist frequently over the space with small modulo size. Then, the erroneous values of α_i, β_i,..., ε_i (i=1,..., N) are derived from the inadequate basis vectors, q_i, r_i. Also, when the degeneracy in modulo size happens, the solutions to α_i, β_i,..., ε_i (i=1,..., N) cannot be solved even by means of the exhaustive search over the small prime divisors of p-1.
社団法人電子情報通信学会の論文
1996-01-25