voter will prove (in the distribution of the secret share phase) to the tellers that his vote is legitimate using the five steps of the interactive proof. Round-optimal and efficient verifiable secret sharing The round complexity of a VSS protocol is defined as the number of communication rounds in its sharing phase; reconstruction can always be done in a single round. There is no 1-round VSS with , regardless of the number of players. The bounds on perfect and efficient VSS protocols is given below. See also Secret sharing Secure multiparty computation Publicly Verifiable Secret Sharing Verifiable computing Bibliography T. Rabin and M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority. In Proceedings of the Twenty-First Annual ACM Symposium on theory of Computing (Seattle, Washington, United States, May 14–17, 1989). Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin, The Round Complexity of Verifiable Secret Sharing and Secure Multicast. In Proceedings of the thirty-third annual ACM symposium on Theory of computing ( Hersonissos, Greece, Pages: 580 - 589, 2001 ) Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan, and Kannan Srinathan, Round-Optimal and Efficient Verifiable Secret Sharing. Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, ( New York, NY, USA, March 4–7, 2006 ) Oded Goldreich, Secure multi-party computation Josh Cohen Benaloh, Secret Sharing Homomorphisms: Keeping Shares of a Secret. Proceedings on Advances in cryptology, CRYPTO '86. pp. 251–260, 1987 References Notes Cryptography