{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:28:15Z","timestamp":1760239695421,"version":"build-2065373602"},"reference-count":85,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2020,12,30]],"date-time":"2020-12-30T00:00:00Z","timestamp":1609286400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"The NSF CISE Research Initiation Initiative (CRII) Award","award":["CNS\u20131566499"],"award-info":[{"award-number":["CNS\u20131566499"]}]},{"name":"NSF SMALL Award","award":["CNS\u20131618822"],"award-info":[{"award-number":["CNS\u20131618822"]}]},{"name":"a Purdue Research Foundation (PRF) Award, and The Center for Science of Information, an NSF Science and Technology Center, Cooperative Agreement","award":["CCF\u20130939370"],"award-info":[{"award-number":["CCF\u20130939370"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Ben-Or and Linial, in a seminal work, introduced the full information model to study collective coin-tossing protocols. Collective coin-tossing is an elegant functionality providing uncluttered access to the primary bottlenecks to achieve security in a specific adversarial model. Additionally, the research outcomes for this versatile functionality has direct consequences on diverse topics in mathematics and computer science. This survey summarizes the current state-of-the-art of coin-tossing protocols in the full information model and recent advances in this field. In particular, it elaborates on a new proof technique that identifies the minimum insecurity incurred by any coin-tossing protocol and, simultaneously, constructs the coin-tossing protocol achieving that insecurity bound. The combinatorial perspective into this new proof-technique yields new coin-tossing protocols that are more secure than well-known existing coin-tossing protocols, leading to new isoperimetric inequalities over product spaces. Furthermore, this proof-technique\u2019s algebraic reimagination resolves several long-standing fundamental hardness-of-computation problems in cryptography. This survey presents one representative application of each of these two perspectives.<\/jats:p>","DOI":"10.3390\/e23010044","type":"journal-article","created":{"date-parts":[[2020,12,30]],"date-time":"2020-12-30T09:35:23Z","timestamp":1609320923000},"page":"44","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computational Hardness of Collective Coin-Tossing Protocols"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4244-8658","authenticated-orcid":false,"given":"Hemanta K.","family":"Maji","sequence":"first","affiliation":[{"name":"Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., and Linial, N. (1985, January 21\u201323). Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values. Proceedings of the 26th Annual Symposium on Foundations of Computer Science, Portland, OR, USA.","DOI":"10.1109\/SFCS.1985.15"},{"key":"ref_2","first-page":"91","article-title":"Collective Coin Flipping","volume":"5","author":"Linial","year":"1989","journal-title":"Adv. Comput. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1525\/9780520319875-014","article-title":"The number of simplices in a complex","volume":"10","author":"Kruskal","year":"1963","journal-title":"Math. Optim. Tech."},{"key":"ref_4","unstructured":"Erd\u00f6s, P., and Katona, G. (1968). A Theorem for Finite Sets, Theory of Graphs, Academic Press."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/S0021-9800(66)80059-5","article-title":"Optimal numberings and isoperimetric problems on graphs","volume":"1","author":"Harper","year":"1966","journal-title":"J. Comb. Theory"},{"key":"ref_6","unstructured":"Santha, M., and Vazirani, U.V. (, January 24\u201326). Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract). Proceedings of the 25th Annual Symposium on Foundations of Computer Science, Singer Island, FL, USA."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O., H\u00e5stad, J., Friedman, J., Rudich, S., and Smolensky, R. (1985, January 21\u201323). The Bit Extraction Problem of t-Resilient Functions (Preliminary Version). Proceedings of the 26th Annual Symposium on Foundations of Computer Science, Portland, OR, USA.","DOI":"10.1109\/SFCS.1985.55"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Vazirani, U.V. (1985, January 6\u20138). Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (Extended Abstract). Proceedings of the 17th Annual ACM Symposium on Theory of Computing, Providence, RI, USA.","DOI":"10.1145\/22145.22186"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Friedman, J. (1992, January 24\u201327). On the Bit Extraction Problem. Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, PA, USA.","DOI":"10.1109\/SFCS.1992.267760"},{"key":"ref_10","first-page":"5","article-title":"Martingales, collective coin flipping and discrete control processes","volume":"1","author":"Cleve","year":"1993","journal-title":"Other Words"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Dachman-Soled, D., Lindell, Y., Mahmoody, M., and Malkin, T. (2011, January 28\u201330). On the Black-Box Complexity of Optimally-Fair Coin Tossing. Proceedings of the 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA.","DOI":"10.1007\/978-3-642-19571-6_27"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Dachman-Soled, D., Mahmoody, M., and Malkin, T. (2014, January 24\u201326). Can Optimally-Fair Coin Tossing Be Based on One-Way Functions?. Proceedings of the 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA.","DOI":"10.1007\/978-3-642-54242-8_10"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/s00145-014-9194-9","article-title":"Limits on the Usefulness of Random Oracles","volume":"29","author":"Haitner","year":"2016","journal-title":"J. Cryptol."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Khorasgani, H.A., Maji, H.K., and Mukherjee, T. (2019, January 1\u20135). Estimating Gaps in Martingales and Applications to Coin-Tossing: Constructions and Hardness. Proceedings of the 17th Theory of Cryptography Conference, Part II, Nuremberg, Germany.","DOI":"10.1007\/978-3-030-36033-7_13"},{"key":"ref_15","first-page":"131","article-title":"Coin Tossing with Lazy Defense: Hardness of Computation Results","volume":"2020","author":"Khorasgani","year":"2020","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/978-3-030-56880-1_21","article-title":"Black-Box Use of One-Way Functions is Useless for Optimal Fair Coin-Tossing","volume":"Volume 12171","author":"Micciancio","year":"2020","journal-title":"Advances in Cryptology\u2014CRYPTO 2020, Part II"},{"key":"ref_17","first-page":"317","article-title":"Weighted voting doesn\u2019t work: A mathematical analysis","volume":"19","author":"Banzhaf","year":"1964","journal-title":"Rutgers L. Rev."},{"key":"ref_18","unstructured":"Liebermann, B. (1971). Control of collectivities and the power of a collectivity to act. Social Choice, Springer."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1145\/321637.321647","article-title":"Chow Parameters in Threshold Logic","volume":"18","author":"Winder","year":"1971","journal-title":"J. ACM"},{"key":"ref_20","unstructured":"Ladner, R.E., and Dwork, C. (2008, January 17\u201320). The Chow parameters problem. Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, BC, Canada."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1137\/090756466","article-title":"The Chow Parameters Problem","volume":"40","author":"Servedio","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Aspnes, J. (1997, January 4\u20136). Lower Bounds for Distributed Coin-Flipping and Randomized Consensus. Proceedings of the 29th Annual ACM Symposium on Theory of Computing, El Paso, TX, USA.","DOI":"10.1145\/258533.258649"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1145\/278298.278304","article-title":"Lower Bounds for Distributed Coin-Flipping and Randomized Consensus","volume":"45","author":"Aspnes","year":"1998","journal-title":"J. ACM"},{"key":"ref_24","unstructured":"Coan, B.A., and Afek, Y. (1998). A Tight Lower Bound for Randomized Synchronous Consensus. ACM Symposium Annual on Principles of Distributed Computing, Association for Computing Machinery."},{"key":"ref_25","unstructured":"Diochnos, D.I., Mahloujifar, S., and Mahmoody, M. (2018, January 3\u20138). Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution. Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, Montreal, QC, Canada."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Mahloujifar, S., Diochnos, D.I., and Mahmoody, M. (February, January 27). The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure. Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, HI, USA.","DOI":"10.1609\/aaai.v33i01.33014536"},{"key":"ref_27","unstructured":"Mahloujifar, S., and Mahmoody, M. (2019, January 22\u201324). Can Adversarially Robust Learning LeverageComputational Hardness?. Proceedings of the Algorithmic Learning Theory, ALT 2019, Chicago, IL, USA."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Etesami, O., Mahloujifar, S., and Mahmoody, M. (2020, January 5\u20138). Computational Concentration of Measure: Optimal Bounds, Reductions, and More. Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, UT, USA.","DOI":"10.1137\/1.9781611975994.21"},{"key":"ref_29","first-page":"519","article-title":"Design & Analysis of Optimal Coin-tossing: New Techniques","volume":"2020","author":"Khorasgani","year":"2020","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref_30","unstructured":"Maji, H.K., and Wang, M. (2020, December 15). Computational Hardness of Optimal Fair Computation: Beyond Minicrypt. Unpublished work. Available online: https:\/\/www.cs.purdue.edu\/homes\/hmaji\/papers\/MajWan20a.pdf."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., and Rudich, S. (1989, January 14\u201317). Limits on the Provable Consequences of One-Way Permutations. Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, USA.","DOI":"10.1145\/73007.73012"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Reingold, O., Trevisan, L., and Vadhan, S.P. (2004, January 19\u201321). Notions of Reducibility between Cryptographic Primitives. Proceedings of the TCC 2004: 1st Theory of Cryptography Conference, Cambridge, MA, USA.","DOI":"10.1007\/978-3-540-24638-1_1"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., and Park, S. (2015, January 6\u201310). Adaptively Secure Coin-Flipping, Revisited. Proceedings of the ICALP 2015: 42nd International Colloquium on Automata, Languages and Programming, Part II, Kyoto, Japan.","DOI":"10.1007\/978-3-662-47666-6_53"},{"key":"ref_34","unstructured":"Blum, M. (1982, January 22\u201325). Coin Flipping by Telephone - A Protocol for Solving Impossible Problems. Proceedings of the COMPCON\u201982, Digest of Papers, Twenty-Fourth IEEE Computer Society International Conference, San Francisco, CA, USA."},{"key":"ref_35","unstructured":"Broder, A.Z., and Dolev, D. (1984, January 24\u201326). Flipping coins in many pockets (Byzantine agreement on uniformly random values). Proceedings of the 25th Annual Symposium on Foundations of Computer Science, Singer Island, FL, USA."},{"key":"ref_36","unstructured":"Awerbuch, B., Blum, M., Chor, B., Goldwasser, S., and Micali, S. (1985). How to implement Bracha\u2019s O (log n) byzantine agreement algorithm. Unpublished."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Cleve, R. (1986, January 28\u201330). Limits on the Security of Coin Flips when Half the Processors Are Faulty (Extended Abstract). Proceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, CA, USA.","DOI":"10.1145\/12130.12168"},{"key":"ref_38","unstructured":"Maji, H.K., Mehta, H., and Wang, M. (2020). On Efficient Distributed Coin-tossing Protocols, Purdue University. Unpublished."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"357","DOI":"10.2748\/tmj\/1178243286","article-title":"Weighted sums of certain dependent random variables","volume":"19","author":"Azuma","year":"1967","journal-title":"Tohoku Math. J."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability Inequalities for Sums of Bounded Random Variables","volume":"58","author":"Hoeffding","year":"1963","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Beimel, A., Haitner, I., Makriyannis, N., and Omri, E. (2018, January 7\u20139). Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling. Proceedings of the 59th Annual Symposium on Foundations of Computer Science, Paris, France.","DOI":"10.1109\/FOCS.2018.00084"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF02125896","article-title":"Some extremal problems arising from discrete control processes","volume":"9","author":"Lichtenstein","year":"1989","journal-title":"Combinatorica"},{"key":"ref_43","unstructured":"Kalai, Y.T., Komargodski, I., and Raz, R. (2018, January 15\u201319). A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols. Proceedings of the 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Haitner, I., and Karidi-Heller, Y. (2020). A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip. arXiv.","DOI":"10.1109\/FOCS46700.2020.00120"},{"key":"ref_45","unstructured":"Cleve, R. (1990, January 11\u201315). Controlled Gradual Disclosure Schemes for Random Bits and Their Applications. Proceedings of the Advances in Cryptology\u2014CRYPTO\u201989, Santa Barbara, CA, USA."},{"key":"ref_46","unstructured":"Impagliazzo, R. (1995, January 19\u201322). A Personal View of Average-Case Complexity. Proceedings of the Tenth Annual Structure in Complexity Theory Conference, Minneapolis, MI, USA."},{"key":"ref_47","unstructured":"Impagliazzo, R., and Luby, M. (November, January 30). One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract). Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, NC, USA."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Levin, L.A., and Luby, M. (1989). Pseudo-random Generation from one-way functions (Extended Abstracts). 21st Annual ACM Symposium on Theory of Computing, ACM Press.","DOI":"10.1145\/73007.73009"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J. (1990). Pseudo-Random Generators under Uniform Assumptions. 22nd Annual ACM Symposium on Theory of Computing, ACM Press.","DOI":"10.1145\/100216.100270"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/S0097539793244708","article-title":"A Pseudorandom Generator from any One-way Function","volume":"28","author":"Impagliazzo","year":"1999","journal-title":"SIAM J. Comput."},{"key":"ref_51","unstructured":"Goldreich, O., Goldwasser, S., and Micali, S. (1982, January 22\u201325). How to Construct Random Functions (Extended Abstract). Proceedings of the COMPCON\u201982, Digest of Papers, Twenty-Fourth IEEE Computer Society International Conference, San Francisco, CA, USA."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1145\/6490.6503","article-title":"How to Construct Random Functions","volume":"33","author":"Goldreich","year":"1986","journal-title":"J. ACM"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1137\/0217022","article-title":"How to construct pseudorandom permutations from pseudorandom functions","volume":"17","author":"Luby","year":"1988","journal-title":"SIAM J. Comput."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF00196774","article-title":"Bit Commitment Using Pseudorandomness","volume":"4","author":"Naor","year":"1991","journal-title":"J. Cryptol."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s001459900037","article-title":"Perfect Zero-Knowledge Arguments for NP Using Any One-Way Permutation","volume":"11","author":"Naor","year":"1998","journal-title":"J. Cryptol."},{"key":"ref_56","unstructured":"Johnson, D.S., and Feige, U. (2007). Statistically-hiding commitment from any one-way function. 39th Annual ACM Symposium on Theory of Computing, ACM Press."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1145\/116825.116852","article-title":"Proofs That Yield Nothing But Their Validity Or All Languages in NP Have Zero-Knowledge Proof Systems","volume":"38","author":"Goldreich","year":"1991","journal-title":"J. ACM"},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Naor, M., and Yung, M. (1989). Universal One-Way Hash Functions and their Cryptographic Applications. 21st Annual ACM Symposium on Theory of Computing, ACM Press.","DOI":"10.1145\/73007.73011"},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Rompel, J. (1990). One-Way Functions are Necessary and Sufficient for Secure Signatures. 22nd Annual ACM Symposium on Theory of Computing, ACM Press.","DOI":"10.1145\/100216.100269"},{"key":"ref_60","unstructured":"Gertner, Y., Kannan, S., Malkin, T., Reingold, O., and Viswanathan, M. (2000, January 12\u201314). The Relationship between Public Key Encryption and Oblivious Transfer. Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA."},{"key":"ref_61","unstructured":"Naor, M. (2014). Limits of random oracles in secure computation. ITCS 2014: 5th Conference on Innovations in Theoretical Computer Science, Association for Computing Machinery."},{"key":"ref_62","unstructured":"Mahmoody, M., Maji, H.K., and Prabhakaran, M. (2014, January 24\u201326). On the Power of Public-Key Encryption in Secure Computation. Proceedings of the TCC 2014: 11th Theory of Cryptography Conference, San Diego, CA, USA."},{"key":"ref_63","doi-asserted-by":"crossref","unstructured":"Chaum, D., Rivest, R.L., and Sherman, A.T. (1982). A Randomized Protocol for Signing Contracts. Advances in Cryptology\u2014CRYPTO\u201982, Plenum Press.","DOI":"10.1007\/978-1-4757-0602-4"},{"key":"ref_64","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1145\/3812.3818","article-title":"A randomized protocol for signing contracts","volume":"28","author":"Even","year":"1985","journal-title":"Commun. ACM"},{"key":"ref_65","doi-asserted-by":"crossref","unstructured":"Haitner, I., and Omri, E. (2011, January 22\u201325). Coin Flipping with Constant Bias Implies One-Way Functions. Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, CA, USA.","DOI":"10.1109\/FOCS.2011.29"},{"key":"ref_66","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B. (2014). Coin flipping of any constant bias implies one-way functions. 46th Annual ACM Symposium on Theory of Computing, ACM Press.","DOI":"10.1145\/2591796"},{"key":"ref_67","doi-asserted-by":"crossref","unstructured":"Moran, T., Naor, M., and Segev, G. (2009, January 15\u201317). An Optimally Fair Coin Toss. Proceedings of the TCC 2009: 6th Theory of Cryptography Conference, San Francisco, CA, USA.","DOI":"10.1007\/978-3-642-00457-5_1"},{"key":"ref_68","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H. (1983, January 7\u20139). Games Against Nature (Extended Abstract). Proceedings of the 24th Annual Symposium on Foundations of Computer Science, Tucson, AZ, USA.","DOI":"10.1109\/SFCS.1983.20"},{"key":"ref_69","doi-asserted-by":"crossref","unstructured":"Maji, H.K., Prabhakaran, M., and Sahai, A. (2010, January 23\u201326). On the Computational Complexity of Coin Flipping. Proceedings of the 51st Annual Symposium on Foundations of Computer Science, Las Vegas, NV, USA.","DOI":"10.1109\/FOCS.2010.64"},{"key":"ref_70","doi-asserted-by":"crossref","unstructured":"Baecher, P., Brzuska, C., and Fischlin, M. (2013, January 1\u20135). Notions of Black-Box Reductions, Revisited. Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2013, Bengaluru, India.","DOI":"10.1007\/978-3-642-42033-7_16"},{"key":"ref_71","doi-asserted-by":"crossref","unstructured":"Cook, S.A. (1971, January 3\u20135). The Complexity of Theorem-Proving Procedures. Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, Shaker Heights, OH, USA.","DOI":"10.1145\/800157.805047"},{"key":"ref_72","doi-asserted-by":"crossref","unstructured":"Miller, R.E., and Thatcher, J.W. (1972). Reducibility Among Combinatorial Problems. Complexity of Computer Computations, Plenum Press.","DOI":"10.1007\/978-1-4684-2001-2"},{"key":"ref_73","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C. (1986, January 27\u201329). How to Generate and Exchange Secrets (Extended Abstract). Proceedings of the 27th Annual Symposium on Foundations of Computer Science, Toronto, ON, Canada.","DOI":"10.1109\/SFCS.1986.25"},{"key":"ref_74","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., and Wigderson, A. (1987, January 25\u201327). How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, NY, USA.","DOI":"10.1145\/28395.28420"},{"key":"ref_75","doi-asserted-by":"crossref","unstructured":"Feige, U., and Shamir, A. (1990, January 13\u201317). Witness Indistinguishable and Witness Hiding Protocols. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA.","DOI":"10.1145\/100216.100272"},{"key":"ref_76","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1137\/S0097539795291562","article-title":"Nonmalleable Cryptography","volume":"30","author":"Dolev","year":"2000","journal-title":"SIAM J. Comput."},{"key":"ref_77","unstructured":"Barak, B. (2002, January 19). Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model. Proceedings of the 43rd Annual Symposium on Foundations of Computer Science, Vancouver, BC, Canada."},{"key":"ref_78","doi-asserted-by":"crossref","unstructured":"Haitner, I., Omri, E., and Zarosim, H. (2013, January 3\u20136). Limits on the Usefulness of Random Oracles. Proceedings of the TCC 2013: 10th Theory of Cryptography Conference, Tokyo, Japan.","DOI":"10.1007\/978-3-642-36594-2_25"},{"key":"ref_79","doi-asserted-by":"crossref","unstructured":"Haitner, I., Makriyannis, N., and Omri, E. (2018, January 11\u201314). On the Complexity of Fair Coin Flipping. Proceedings of the TCC 2018: 16th Theory of Cryptography Conference, Part I, Panaji, India.","DOI":"10.1007\/978-3-030-03807-6_20"},{"key":"ref_80","doi-asserted-by":"crossref","unstructured":"Kilian, J. (2000, January 21\u201323). More general completeness theorems for secure two-party computation. Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, USA.","DOI":"10.1145\/335305.335342"},{"key":"ref_81","doi-asserted-by":"crossref","unstructured":"Barak, B., and Mahmoody-Ghidary, M. (2009, January 16\u201320). Merkle Puzzles Are Optimal\u2014An O(n2)-Query Attack on Any Key Exchange from a Random Oracle. Proceedings of the Advances in Cryptology\u2014CRYPTO 2009, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-642-03356-8_22"},{"key":"ref_82","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/S0166-218X(99)00082-7","article-title":"On an Isoperimetric Problem for Hamming Graphs","volume":"95","author":"Harper","year":"1999","journal-title":"Discret. Appl. Math."},{"key":"ref_83","unstructured":"Jerrum, M. (1985, January 15\u201319). Random Generation of Combinatorial Structures from a Uniform Distribution (Extended Abstract). Proceedings of the Automata, Languages and Programming, 12th Colloquium, Nafplion, Greece."},{"key":"ref_84","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","article-title":"Random Generation of Combinatorial Structures from a Uniform Distribution","volume":"43","author":"Jerrum","year":"1986","journal-title":"Theor. Comput. Sci."},{"key":"ref_85","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1006\/inco.2000.2885","article-title":"Uniform Generation of NP-Witnesses Using an NP-Oracle","volume":"163","author":"Bellare","year":"2000","journal-title":"Inf. Comput."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/1\/44\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:47:57Z","timestamp":1760179677000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/1\/44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,30]]},"references-count":85,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["e23010044"],"URL":"https:\/\/doi.org\/10.3390\/e23010044","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2020,12,30]]}}}