{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T07:17:21Z","timestamp":1772695041559,"version":"3.50.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"11s","license":[{"start":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T00:00:00Z","timestamp":1643587200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"SERB MATRICS","award":["2020"],"award-info":[{"award-number":["2020"]}]},{"name":"Google India AI\/ML Research Award 2020"},{"name":"DST National Mission on Interdisciplinary Cyber-Physical Systems (NM-CPS) 2020"},{"name":"National Security Council, India"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p><jats:italic>Verifiable Secret-Sharing<\/jats:italic>(VSS) is a fundamental primitive in secure distributed computing. It is used as a building block in several distributed computing tasks, such as Byzantine agreement and secure multi-party computation. In this article, we consider VSS schemes with<jats:italic>perfect<\/jats:italic>security, tolerating<jats:italic>computationally unbounded<\/jats:italic>adversaries. We comprehensively survey the existing perfectly secure VSS schemes in three different communication settings, namely, synchronous, asynchronous, and hybrid setting and provide full details of the existing schemes in these settings. The aim of this survey is to provide a clear knowledge and foundation to researchers who are interested in knowing and extending the state-of-the-art perfectly secure VSS schemes.<\/jats:p>","DOI":"10.1145\/3512344","type":"journal-article","created":{"date-parts":[[2022,2,7]],"date-time":"2022-02-07T22:39:32Z","timestamp":1644273572000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["A Survey on Perfectly Secure Verifiable Secret-sharing"],"prefix":"10.1145","volume":"54","author":[{"given":"Anirudh","family":"Chandramouli","sequence":"first","affiliation":[{"name":"International Institute of Information Technology Bangalore, Hosur Road, Bangalore India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2428-9537","authenticated-orcid":false,"given":"Ashish","family":"Choudhury","sequence":"additional","affiliation":[{"name":"International Institute of Information Technology Bangalore, Hosur Road, Bangalore India"}]},{"given":"Arpita","family":"Patra","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore India"}]}],"member":"320","published-online":{"date-parts":[[2022,9,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1145\/3382734.3405722","volume-title":"PODC","author":"Abraham I.","year":"2020","unstructured":"I. Abraham, D. Dolev, and G. Stern. 2020. Revisiting asynchronous fault tolerant computation with optimal resilience. In PODC. ACM, 139\u2013148."},{"key":"e_1_3_2_3_2","first-page":"106","volume-title":"IEEE S&P","author":"Abraham I.","year":"2020","unstructured":"I. Abraham, D. Malkhi, K. Nayak, L. Ren, and M. Yin. 2020. Sync HotStuff: Simple and practical synchronous state machine replication. In IEEE S&P. IEEE, 106\u2013118."},{"key":"e_1_3_2_4_2","first-page":"1277","volume-title":"FOCS","author":"Applebaum B.","year":"2020","unstructured":"B. Applebaum, E. Kachlon, and A. Patra. 2020. The round complexity of perfect MPC with active security and optimal resiliency. In FOCS. IEEE, 1277\u20131284."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-015-9214-4"},{"key":"e_1_3_2_6_2","first-page":"590","volume-title":"ASIACRYPT (Lecture Notes in Computer Science)","author":"Backes M.","year":"2011","unstructured":"M. Backes, A. Kate, and A. Patra. 2011. Computational verifiable secret sharing revisited. In ASIACRYPT (Lecture Notes in Computer Science), Vol. 7073. Springer, 590\u2013609."},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1145\/3288599.3288600","volume-title":"ICDCN","author":"Bangalore L.","year":"2019","unstructured":"L. Bangalore, A. Choudhury, and G. Garimella. 2019. Round efficient computationally secure multi-party computation revisited. In ICDCN. ACM, 292\u2013301."},{"key":"e_1_3_2_8_2","first-page":"376","volume-title":"ASIACRYPT (Lecture Notes in Computer Science)","author":"Beerliov\u00e1-Trub\u00edniov\u00e1 Z.","year":"2007","unstructured":"Z. Beerliov\u00e1-Trub\u00edniov\u00e1 and M. Hirt. 2007. Simple and efficient perfectly-secure asynchronous MPC. In ASIACRYPT (Lecture Notes in Computer Science), Vol. 4833. Springer, 376\u2013392."},{"key":"e_1_3_2_9_2","first-page":"213","volume-title":"TCC (Lecture Notes in Computer Science)","author":"Beerliov\u00e1-Trub\u00edniov\u00e1 Z.","year":"2008","unstructured":"Z. Beerliov\u00e1-Trub\u00edniov\u00e1 and M. Hirt. 2008. Perfectly-secure MPC with linear communication complexity. In TCC (Lecture Notes in Computer Science), Vol. 4948. Springer, 213\u2013230."},{"key":"e_1_3_2_10_2","first-page":"211","volume-title":"PODC","author":"Beerliov\u00e1-Trub\u00edniov\u00e1 Z.","year":"2010","unstructured":"Z. Beerliov\u00e1-Trub\u00edniov\u00e1, M. Hirt, and J. B. Nielsen. 2010. On the theoretical gap between synchronous and asynchronous MPC protocols. In PODC. ACM, 211\u2013218."},{"key":"e_1_3_2_11_2","first-page":"11","volume-title":"IWCC (Lecture Notes in Computer Science)","author":"Beimel A.","year":"2011","unstructured":"A. Beimel. 2011. Secret-sharing schemes: A survey. In IWCC (Lecture Notes in Computer Science), Vol. 6639. Springer, 11\u201346."},{"key":"e_1_3_2_12_2","first-page":"52","volume-title":"STOC","author":"Ben-Or M.","year":"1993","unstructured":"M. Ben-Or, R. Canetti, and O. Goldreich. 1993. Asynchronous secure computation. In STOC. ACM, 52\u201361."},{"key":"e_1_3_2_13_2","first-page":"1","volume-title":"STOC","author":"Ben-Or M.","year":"1988","unstructured":"M. Ben-Or, S. Goldwasser, and A. Wigderson. 1988. Completeness theorems for non-cryptographic fault-tolerant distributed computation (Extended Abstract). In STOC. ACM, 1\u201310."},{"key":"e_1_3_2_14_2","first-page":"183","volume-title":"PODC","author":"Ben-Or M.","year":"1994","unstructured":"M. Ben-Or, B. Kelmer, and T. Rabin. 1994. Asynchronous secure computations with optimal resilience (Extended Abstract). In PODC. ACM, 183\u2013192."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/MARK.1979.8817296"},{"key":"e_1_3_2_16_2","first-page":"154","volume-title":"PODC","author":"Bracha G.","year":"1984","unstructured":"G. Bracha. 1984. An asynchronous [(n-1)\/3]-Resilient consensus protocol. In PODC. ACM, 154\u2013162."},{"key":"e_1_3_2_17_2","volume-title":"Studies in Secure Multiparty Computation and Applications","author":"Canetti R.","year":"1995","unstructured":"R. Canetti. 1995. Studies in Secure Multiparty Computation and Applications. Ph.D. Dissertation. Weizmann Institute."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3402457"},{"key":"e_1_3_2_19_2","first-page":"383","volume-title":"FOCS","author":"Chor B.","year":"1985","unstructured":"B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. 1985. Verifiable secret sharing and achieving simultaneity in the presence of faults (Extended Abstract). In FOCS. IEEE Computer Society, 383\u2013395."},{"key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1145\/3382734.3404503","volume-title":"PODC","author":"Choudhury A.","year":"2020","unstructured":"A. Choudhury. 2020. Brief announcement: Almost-surely terminating asynchronous byzantine agreement protocols with a constant expected running time. In PODC. ACM, 169\u2013171."},{"key":"e_1_3_2_21_2","first-page":"832","volume-title":"INDOCRYPT (Lecture Notes in Computer Science)","author":"Choudhury A.","year":"2020","unstructured":"A. Choudhury and A. Hegde. 2020. High throughput secure MPC over small population in hybrid networks (Extended Abstract). In INDOCRYPT (Lecture Notes in Computer Science), Vol. 12578. Springer, 832\u2013855."},{"key":"e_1_3_2_22_2","first-page":"388","volume-title":"DISC (Lecture Notes in Computer Science)","author":"Choudhury A.","year":"2013","unstructured":"A. Choudhury, M. Hirt, and A. Patra. 2013. Asynchronous multiparty computation with linear communication complexity. In DISC (Lecture Notes in Computer Science), Vol. 8205. Springer, 388\u2013402."},{"key":"e_1_3_2_23_2","first-page":"143","volume-title":"ICITS (Lecture Notes in Computer Science)","author":"Choudhury A.","year":"2011","unstructured":"A. Choudhury, K. Kurosawa, and A. Patra. 2011. The round complexity of perfectly secure general VSS. In ICITS (Lecture Notes in Computer Science), Vol. 6673. Springer, 143\u2013162."},{"key":"e_1_3_2_24_2","first-page":"786","volume-title":"INDOCRYPT (Lecture Notes in Computer Science)","author":"Choudhury A.","year":"2020","unstructured":"A. Choudhury and N. Pappu. 2020. Perfectly-secure asynchronous MPC for general adversaries (Extended Abstract). In INDOCRYPT (Lecture Notes in Computer Science), Vol. 12578. Springer, 786\u2013809."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2614685"},{"key":"e_1_3_2_26_2","first-page":"311","volume-title":"EUROCRYPT (Lecture Notes in Computer Science)","author":"Cramer R.","year":"1999","unstructured":"R. Cramer, I. Damg\u00e5rd, S. Dziembowski, M. Hirt, and T. Rabin. 1999. Efficient multiparty computations secure against an adaptive adversary. In EUROCRYPT (Lecture Notes in Computer Science), Vol. 1592. Springer, 311\u2013326."},{"key":"e_1_3_2_27_2","first-page":"316","volume-title":"EUROCRYPT (Lecture Notes in Computer Science)","author":"Cramer R.","year":"2000","unstructured":"R. Cramer, I. Damg\u00e5rd, and U. M. Maurer. 2000. General secure multi-party computation from any linear secret-sharing scheme. In EUROCRYPT (Lecture Notes in Computer Science), Vol. 1807. Springer Verlag, 316\u2013334."},{"key":"e_1_3_2_28_2","first-page":"160","volume-title":"PKC (Lecture Notes in Computer Science)","author":"Damg\u00e5rd I.","year":"2009","unstructured":"I. Damg\u00e5rd, M. Geisler, M. Kr\u00f8igaard, and J. B. Nielsen. 2009. Asynchronous multiparty computation: Theory and implementation. In PKC (Lecture Notes in Computer Science), Vol. 5443. Springer, 160\u2013179."},{"key":"e_1_3_2_29_2","first-page":"572","volume-title":"CRYPTO (Lecture Notes in Computer Science)","author":"Damg\u00e5rd I.","year":"2007","unstructured":"I. Damg\u00e5rd and J. B. Nielsen. 2007. Scalable and unconditionally secure multiparty computation. In CRYPTO (Lecture Notes in Computer Science), Vol. 4622. Springer, 572\u2013590."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/138027.138036"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790187084"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90033-3"},{"key":"e_1_3_2_33_2","first-page":"329","volume-title":"TCC (Lecture Notes in Computer Science)","author":"Fitzi M.","year":"2006","unstructured":"M. Fitzi, J. A. Garay, S. Gollakota, C. Pandu Rangan, and K. Srinathan. 2006. Round-optimal and efficient verifiable secret sharing. In TCC (Lecture Notes in Computer Science), Vol. 3876. Springer, 329\u2013342."},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1145\/380752.380853","volume-title":"STOC","author":"Gennaro R.","year":"2001","unstructured":"R. Gennaro, Y. Ishai, E. Kushilevitz, and T. Rabin. 2001. The round complexity of verifiable secret sharing and secure multicast. In STOC. ACM, 580\u2013589."},{"key":"e_1_3_2_35_2","volume-title":"The Foundations of Cryptography - Volume 2, Basic Applications","author":"Goldreich O.","year":"2004","unstructured":"O. Goldreich. 2004. The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press."},{"key":"e_1_3_2_36_2","first-page":"499","volume-title":"CRYPTO (Lecture Notes in Computer Science)","author":"Guo Y.","year":"2019","unstructured":"Y. Guo, R. Pass, and E. Shi. 2019. Synchronous, with a chance of partition tolerance. In CRYPTO (Lecture Notes in Computer Science), Vol. 11692. Springer, 499\u2013529."},{"key":"e_1_3_2_37_2","volume-title":"Multi Party Computation: Efficient Protocols, General Adversaries, and Voting","author":"Hirt M.","year":"2001","unstructured":"M. Hirt. 2001. Multi Party Computation: Efficient Protocols, General Adversaries, and Voting. Ph.D. Dissertation. ETH Zurich, Z\u00fcrich, Switzerland."},{"key":"e_1_3_2_38_2","first-page":"99","volume-title":"GLOBECOM","author":"Ito M.","year":"1987","unstructured":"M. Ito, A. Saito, and T. Nishizeki. 1987. Secret sharing schemes realizing general access structures). In GLOBECOM. IEEE Computer Society, 99\u2013102."},{"key":"e_1_3_2_39_2","first-page":"445","volume-title":"CRYPTO (Lecture Notes in Computer Science)","author":"Katz J.","year":"2006","unstructured":"J. Katz and C. Y. Koo. 2006. On expected constant-round protocols for byzantine agreement. In CRYPTO (Lecture Notes in Computer Science), Vol. 4117. Springer, 445\u2013462."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.03.007"},{"key":"e_1_3_2_41_2","first-page":"431","volume-title":"ASIACRYPT (Lecture Notes in Computer Science)","author":"Kumaresan R.","year":"2010","unstructured":"R. Kumaresan, A. Patra, and C. Pandu Rangan. 2010. The round complexity of verifiable secret sharing: The statistical case. In ASIACRYPT (Lecture Notes in Computer Science), Vol. 6477. Springer, 431\u2013447."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/090755886"},{"key":"e_1_3_2_43_2","first-page":"439","volume-title":"TCC (Lecture Notes in Computer Science)","author":"Liu-Zhang C.","year":"2020","unstructured":"C. Liu-Zhang and U. Maurer. 2020. Synchronous constructive cryptography. In TCC (Lecture Notes in Computer Science), Vol. 12551. Springer, 439\u2013472."},{"key":"e_1_3_2_44_2","volume-title":"Distributed Algorithms","author":"Lynch N. A.","year":"1996","unstructured":"N. A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann."},{"key":"e_1_3_2_45_2","volume-title":"The Theory of Error Correcting Codes","author":"MacWilliams F. J.","year":"1978","unstructured":"F. J. MacWilliams and N. J. A. Sloane. 1978. The Theory of Error Correcting Codes. North-Holland Publishing Company."},{"key":"e_1_3_2_46_2","first-page":"1041","volume-title":"CCS","author":"Malkhi D.","year":"2019","unstructured":"D. Malkhi, K. Nayak, and L. Ren. 2019. Flexible byzantine fault tolerance. In CCS. ACM, 1041\u20131053."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.03.020"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/358746.358762"},{"key":"e_1_3_2_49_2","first-page":"487","volume-title":"CRYPTO (Lecture Notes in Computer Science)","author":"Patra A.","year":"2009","unstructured":"A. Patra, A. Choudhary, T. Rabin, and C. P. Rangan. 2009. The round complexity of verifiable secret sharing revisited. In CRYPTO (Lecture Notes in Computer Science), Vol. 5677. Springer, 487\u2013504."},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0200-5"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-013-9172-7"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2827360"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_3_2_54_2","first-page":"522","volume-title":"EUROCRYPT (Lecture Notes in Computer Science)","author":"Pedersen T. P.","year":"1991","unstructured":"T. P. Pedersen. 1991. A threshold cryptosystem without a trusted party (Extended Abstract). In EUROCRYPT (Lecture Notes in Computer Science), Vol. 547. Springer, 522\u2013526."},{"key":"e_1_3_2_55_2","first-page":"73","volume-title":"STOC","author":"Rabin T.","year":"1989","unstructured":"T. Rabin and M. Ben-Or. 1989. Verifiable secret sharing and multiparty protocols with honest majority (Extended Abstract). In STOC. ACM, 73\u201385."},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3512344","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3512344","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:58Z","timestamp":1750183798000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3512344"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,31]]},"references-count":55,"journal-issue":{"issue":"11s","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3512344"],"URL":"https:\/\/doi.org\/10.1145\/3512344","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,31]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}