Weakness of Kurosawa and Heng’s WitnessIndistinguishable Protocol Based on DH-tuple

The concept of witness indistinguishabilityand witness hiding was introduced by Feige and Shamirin 1990. Recently, B. Kurosawa and S.H. Heng proposed3-move undeniable signature scheme at Eurocrypt 2005,which has the confirmation and disvowal protocols forproving the message-signature pair is or is not valid respectively.They also proposed an new DH-tuple Witnessindistinguishable (WI) protocol, which is the foundationof the comfirmation protocol in this new undeniable signaturescheme. In this paper, we will first show a weaknessin Kurosawa and Heng’s witness indistinguishable protocol.In general, there are two or more witnesses in a WTprotocol. The weakness in Kurosawa and Heng’s WI protocolis that a prover with a witness, but does not konwanother witness, can forge to produce a cheating proof,which is considered to be from another witness. So, fromthe concept of witness hiding, there will be an new witness,which is difference from the two original witnesses. We alsoinvestigate the reason cuased the weakness in Kurosawa etal.’s protocol.