{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:57Z","timestamp":1787337477692,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We initiate an investigation of general fault-tolerant distributed computation in the full-information model. In the full information model no restrictions are made on the computational power of the faulty parties or the information available to them. (Namely, the faulty players may be infinitely powerful and there are no private channels connecting pairs of honest players).<\/jats:p>\n                  <jats:p>Previous work in this model has concentrated on the particular problem of simulating a single bounded-bias global coin flip (e.g., Ben-Or and Linial [Randomness and Computation, S. Micali, ed., JAI Press, Greenwich, CT, 1989, pp. 91--115] and Alon and Naor [SIAM J. Comput., 22 (1993), pp. 403--417]). We widen the scope of investigation to the general question of how well arbitrary fault-tolerant computations can be performed in this model. The results we obtain should be considered as first steps in this direction.<\/jats:p>\n                  <jats:p>We present efficient two-party protocols for fault-tolerant computation of any bivariate function. We prove that the advantage of a dishonest player in these protocols is the minimum one possible (up to polylogarithmic factors).<\/jats:p>\n                  <jats:p>We also present efficient m-party fault-tolerant protocols for sampling a general distribution (\\mbox{$m\\geq2$}). Such an algorithm seems an important building block towards the design of efficient multiparty protocols for fault-tolerant computation of multivariate functions.<\/jats:p>","DOI":"10.1137\/s0097539793246689","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"506-544","source":"Crossref","is-referenced-by-count":30,"title":["Fault-tolerant Computation in the Full Information Model"],"prefix":"10.1137","volume":"27","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shafi","family":"Goldwasser","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nathan","family":"Linial","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0222030"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"D. Beaver and S. Goldwasser,\n                      Distributed Computation with Faulty Majority\n                      , 30th FOCS, 1989, pp. 468\u2013473.","DOI":"10.1109\/SFCS.1989.63520"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. Ben\u2010or, S. Goldwasser, and A. Wigderson,\n                      Completeness Theorems for Non\u2010Cryptographic Fault\u2010Tolerant Distributed Computation\n                      , Proc. of 20th STOC, 1988, pp. 1\u201310.","DOI":"10.1145\/62212.62213"},{"key":"R4","unstructured":"M. Ben\u2010or and N. Linial,\n                      Collective coin flipping\n                      , Randomness and Computation, S. Micali, ed., JAI Press, 1989, pp. 91\u2013115."},{"key":"R5","unstructured":"M. Ben\u2010Or, N. Linial, M. Saks, Collective coin flipping and other models of imperfect randomness, Colloq. Math. Soc. J\u00e1nos Bolyai, Vol. 52, North\u2010Holland, Amsterdam, 1988, 75\u201311294f:68076"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0217015"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"D. Chaum, C. Crepeau, and I. Damg\u00e5rd,\n                      Multiparty Unconditionally Secure Protocols\n                      , Proc. of 20th STOC, 1988, pp. 11\u201319.","DOI":"10.1145\/62212.62214"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0404004"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"J. Cooper and N. Linial,\n                      Fast perfect\u2010information leader election protocol with linear immunity\n                      , Combinatorica, accepted for publication. Extended abstract: 25th Symposium on the Theory of Computing, San Diego, 1993, pp. 662\u2013671.","DOI":"10.1145\/167088.167258"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd,\n                      Interactive Hashing can Simplify Zero\u2010Knowledge Protocol Design Without Computational Assumptions\n                      , Advances in Cryptology\u2014Proceedings of Crypto93, pp. 100\u2013109.","DOI":"10.1007\/3-540-48329-2_9"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Z. Galil, S. Haber, and M. Yung,\n                      Cryptographic Computation: Secure Faulty\u2010Tolerant Protocols and the Public Key Model\n                      , Advances in Cryptology\u2014Proceedings of Crypto87, pp. 135\u2013155.","DOI":"10.1007\/3-540-48184-2_10"},{"key":"R12","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1137\/S0097539793246689","volume":"27","author":"Goldreich Oded","year":"1998","journal-title":"SIAM J. Comput."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson,\n                      How to Play Any Mental Game\n                      , Proc. of 19th STOC, 1987, pp. 218\u2013229.","DOI":"10.1145\/28395.28420"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"S. Goldwasser and L. A. Levin,\n                      Fair Computation of General Functions in Presence of Immoral Majority\n                      , Advances in Cryptology\u2014Proceedings of Crypto90, pp. 77\u201393.","DOI":"10.1007\/3-540-38424-3_6"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"J. Kahn, G. Kalai, and N. Linial,\n                      The influence of variables on boolean functions\n                      , 29th FOCS, 1988, pp. 68\u201380.","DOI":"10.1109\/SFCS.1988.21923"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"J. Kilian,\n                      Founding Cryptography on Oblivious Transfer\n                      , Proc. of 20th STOC, pp. 20\u201329, 1988.","DOI":"10.1145\/62212.62215"},{"key":"R18","unstructured":"M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung,\n                      Perfect Zero\u2010Knowledge Arguments for NP can be Based on General Complexity Assumptions\n                      , Advances in Cryptology\u2013Proceedings of Crypto92, Springer\u2010Verlag Lecture Notes in Computer Science. To appear in\n                      J. Cryptology\n                      ."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky, S. Rajagopalan, and U. Vazirani,\n                      Simple and Efficient Leader Election in the Full Information Model\n                      , Proc. of 26th STOC, 1994, pp. 234\u2013242.","DOI":"10.1145\/195058.195141"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung, Fair games against an all\u2010powerful adversary, DIMACSSer. Discrete Math. Theoret. Comput. Sci., Vol. 13, Amer. Math. Soc., Providence, RI, 1993, 155\u201316994j:94017","DOI":"10.1090\/dimacs\/013\/09"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky, R. Venkatesan, and M. Yung,\n                      Interactive Hashing Simplifies Zero\u2010Knowledge Protocol Design\n                      , Eurocrypt93, pp. 267\u2013273.","DOI":"10.1007\/3-540-48285-7_23"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"M. Santha and U. V. Vazirani,\n                      Generating Quasi\u2010Random Sequences from Slightly\u2010Random Sources\n                      , 25th Symp. on Foundation of Computer Science, 1984, pp. 434\u2013440.","DOI":"10.1109\/SFCS.1984.715945"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"U. V. Vazirani and V. V. Vazirani,\n                      Random Polynomial Time is equal to Slightly\u2010Random Polynomial Time\n                      , 26th Symp. on Foundation of Computer Science, 1985, pp. 417\u2013428.","DOI":"10.1109\/SFCS.1985.45"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Andrew Yao, Protocols for secure computations, IEEE, New York, 1982, 160\u2013164780394","DOI":"10.1109\/SFCS.1982.38"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"A. C. Yao,\n                      How to Generate and Exchange Secrets\n                      , 27th FOCS, 1986, pp. 162\u2013167.","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793246689","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:14Z","timestamp":1787335934000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793246689"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539793246689"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793246689","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}