Practical generation of common random strings for secure multiparty computations over the Internet

  • István Vajda Technical University of Budapest, Dept. of Informatics
Keywords: secure coin-tossing; cryptographic protocols; universal composition; source of entropy


It is known that most of the interesting multiparty cryptographic tasks cannot be implemented securely without trusted setup in a general concurrent network environment like the Internet. We need an appropriate trusted third party to solve this problem.  An important trusted setup is a public random string shared by the parties. We present a practical n-bit coin toss protocol for provably secure implementation of such setup. Our idea is inviting external peers into the execution of the protocol to establish an honest majority among the parties. We guarantee security in the presence of an unconditional, static, malicious adversary. Additionally, we present an original practical idea of using live public radio broadcast channels for the generation of common physical random source.  


(1) Canetti, R. (2001) ‘Universally Composable Security: A New Paradigm for Cryptographic Protocols’, In 42nd FOCS, pp. 136-145

(2) Blum, M., Feldman, P. and Micali, S. (1988) ‘Non-Interactive Zero-Knowledge and Its Applications’, Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC 1988). pp.103–112

(3) Canetti, R., Lindell, Y., Ostrovsky R. and Sahai A. (2002) ‘Universally Composable Two-Party and Multi-Party Secure Computation’, In Proc of the 34th STOC, pp.494-503

(4) Canetti, R. and Fischlin, M. (2001) ’Universally Composable Commitments’, Crypto 2001, LNCS, vol. 2139, pp. 19-40

(5) Canetti, R., Kushilevitz E. and Lindell, Y. (2006) ’On the Limitations of Universal Composable Two-Party Computation Without Set-Up Assumptions’, Journal of Cryptology, Vol.19 No. 2, pp. 135-167

(6) Canetti, R., Pass, R. and Shelat, A. (2007) ‘Cryptography from Sunspots: How to Use an Imperfect Reference String’. In FOCS '07 , pp. 249-259

(7) Cano, P., Batlle E., Mayer, H. and Neuschmied H. (2002) ‘Robust sound modeling for song detection in broadcast audio’, Proc. 112th Audio Engineering Society Convention (AES)

(8) Cleve R. (1986) ’Limits on the security of coin ips when half the processors are faulty’, In Proc. of the 18th STOC, pp. 364-369

(9) Damgaard I. (2000) ’Efficient Concurrent Zero-Knowledge in the Auxiliary String Model’. In Proc. of EUROCRYPT 2000, pp. 418-430

(10) Goldreich, O (2004) ’Foundations of Cryptography Vol. I. - Basic Tools’, Cambridge University Press, 2004.

(11) Goldreich, O (2004) ’Foundations of Cryptography Vol. II - Basic Applications’, Cambridge University Press,

(12) Lindell, Y. (2003) ‘General Composition and Universal Composability in Secure Multiparty Computation’, In Proc. of the 44th FOCS. pp. 394–403

(13) Lindell, Y. (2003) ’Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation’, Journal of Cryptology, Vol.16 No.3, pp 143–184.

(14) Rabin, T. and Ben-Or, M. (1989) ’Verifiable secret sharing and multiparty protocols with honest majority’, In Proc. of the 21st STOC, pp. 73-85

(15) Zhang X., Hongxiang S., Zhang H., Qiaoyan W. and Haixia X. (2010) ’A Zhang X., Hongxiang S., Zhang H., Qiaoyan W. and Haixia X. (2010) ’A constant-round perfect parallel coin-tossing protocol’, In Proc. of the 2010

IEEE International Conference on Progress in Informatics and Computing, Vol. 1, pp. 423-426

How to Cite
Vajda, I. (2020). Practical generation of common random strings for secure multiparty computations over the Internet. Transactions on Networks and Communications, 8(6), 01-15.