Abstract:To provide effective privacy protection for participants in network communication, an improved k-anonymous message transmission protocol was proposed based on Ahn’s work. Some secret sharing techniques were employed to set up session keys for every user within a group and the sum of these keys was kept equal to zero. Each user was required to broadcast a single message encrypted by his secret session key in a communication round. The meaningful anonymous messages could be recovered by multiplying all the broadcast data together. A sub-protocol with constant round complexity was also constructed based on the witness indistinguishable proof techniques to guarantee fairness. The computation and communication complexity of the improved transmission sub-protocol was reduced by a factor of M (the number of users within a group), and that of the sub protocol with fairness by a factor of λ (the security parameter). It can be proved that the anonymity of the improved protocol is based on the Decisional Diffie-Hellman assumption.