A system and method for anonymous message broadcasting uses secret shares of a first vector of size i and a second vector of size j from each client device with a message in an anonymity set of client devices. Each secret share of the first and second vectors is received at each of a plurality of message broadcasting servers to construct a matrix M of i and j dimensions, which is added to a matrix A of i and j dimensions maintained at that message broadcasting server. The matrix A at each message broadcasting server is shared with the other message broadcasting servers and a final matrix A is constructed using the shared matrices A at each message broadcasting server, wherein the final matrix A includes the messages from the client devices in the anonymity set. The messages in the final matrix A are broadcasted from the message broadcasting servers.