Research of Trace Equivalence Relation on XTR

The trace equivalence relation is analyzed and proved by the property of cyclic group, and the XTR security decreasing caused by the equivalence relation is discussed. To cope with this problem, an improved algorithm was proposed to eliminate the equivalence relation effectively. The improved algorithm is compatible with the old speedup algorithm. Furthermore, the algorithm is more effective to improve the degree of XTR security. In the last, the algorithm is used in an improved signature scheme with Message Recovery, and the computation and communication cost are analyzed. The results show that the computation cost is on average more half than the old, but the communication cost only need an additional parameter.