In online surveys, many people are not willing to provide true answers due to privacy concerns. Thus, anonymity is important for online message collection. Existing solutions let each member blindly shuffle the submitted messages by using the IND-CCA2 secure cryptosystem. In the end, all messages are randomly shuffled and no one knows the message order. However, the heavy computational overhead and linear communication rounds make it only useful for small groups. In this paper, we propose an efficient anonymous message submission protocol aimed at a practical group size. Our protocol is based on a simplified secret sharing scheme and a symmetric key cryptosystem. We propose a novel method to let all members secretly aggregate their messages into a message vector such that a member knows nothing about other members’ message positions.We provide a theoretical proof showing that our protocol is anonymous under malicious attacks. We then conduct a thorough analysis of our protocol, showing that our protocol is computationally more efficient than existing solutions and results in a constant communication rounds with a high probability.
It is easy to anonymously submit messages in the real world when compared with the same task in a public network. For example, in the real world, the collector just hands out the questionnaires and lets the group members fill them out. When the members submit their questionnaires, they first put them in a ballot box and then shake the box to shuffle the sheets before they submit them to the collector. However, if the collector wants to do it online, it becomes challenging because 1) a secure ballot box, which is actually a third storage facility, is hard to find, and 2) the shaking and shuffling activities are under all members’ surveillance, which is difficult to implement in a distributed network.
We propose a novel anonymous position application technique, which can help every group member find a position in a position vector in a manner that every member is oblivious to the positions of the other members. This technique can be done in a few communication rounds with a high probability of success (2 rounds with a 95% success probability).
We propose an efficient anonymous message submission protocol for groups with a practical scale. Our protocol runs in polynomial time in the group size and constant communication rounds with a high probability.
We prove that our protocol is anonymous and collusion resistant under malicious attacks. The security of our protocol is based on the security of the secret sharing scheme and the symmetric key cryptosystem.
We analyze the performance of our protocol from the aspects of security and efficiency. Our simulation results show that our protocol is more efficient than the existing works, especially when the group size is large. More specifically, the computation of the collector in our protocol can achieve linear time complexity compared to the polynomial time complexity.