Article

Completely fair SFE and coalition-safe cheap talk

Authors:

Abhi ShelatAuthors Info & Claims

PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

Pages 1 - 10

https://doi.org/10.1145/1011767.1011769

Published: 25 July 2004 Publication History

Abstract

Secure function evaluation (SFE) enables a group of players, by themselves, to evaluate a function on private inputs as securely as if a trusted third party had done it for them. A completely fair SFE is a protocol in which, conceptually, the function values are learned atomically.We provide a completely fair SFE protocol which is secure for any number of malicious players, using a novel combination of computational and physical channel assumptions.We also show how completely fair SFE has striking applications togame theory. In particular, it enables "cheap-talk" protocol that

(a) achieve correlated-equilibrium payoffs in any game,

(b) are the first protocols which provably give no additional power to any coalition of players, and

(c) are exponentially more efficient than prior counterparts.

References

[1]

R. Aumann. Subjectivity and correlation in randomized strategies. J. Math. Econ., 1:67--96, 1974.]]

[2]

I. Bàràny. Fair distribution protocols or how the players replace fortune. Mathematics of Operation Research, 17:327--341, May 1992.]]

Digital Library

[3]

M. Ben-Or, O. Goldreich, S. Goldwasser, J. Hastad, J. K. S. Micali, and P. Rogaway. Everything provable is provable in zero-knowledge. In Proc. CRYPTO 88, pages 37--56. Springer Verlag, 1988.]]

Digital Library

[4]

M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for fault-tolerant distributed computing. In Proc. 20th STOC, pages 1--10. ACM, 1988.]]

Digital Library

[5]

E. Ben-Porath. Correlation without mediation: Expanding the set of equilibria outcomes by "cheap" pre-play procedures. Journal of Economic Theory, 80:108--122, 1998.]]

[6]

M. Blum. Three Applications of the Oblivious Transfer: Part I: Coin Flipping by the telephone; Part II: How to Exchange Secrets; Part III: How to Send Certified Electronic Mail. University of California, Berkeley, 1981.]]

[7]

M. Blum, A. D. Santis, S. Micali, and G. Persiano. Noninteractive zero-knowledge. SIAM J. Computing, 20(6):1084--1118, 1991.]]

Digital Library

[8]

R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In Proc. 42nd FOCS, pages 136--147. IEEE Computer Society, 2001.]]

Digital Library

[9]

R. Canetti, U. Feige, O. Goldreich, and M. Naor. Adaptively secure multi-party computation. In Proc. 28th annual ACM Symposium on Theory of Computing, pages 639--648. ACM Press, 1996.]]

Digital Library

[10]

D. Chaum, C. Crepeau, and I. Damgård. Multi-party unconditionally secure protocols. In Proc. 20th STOC, Chicago, 1988. ACM.]]

Digital Library

[11]

R. Cleve. Limits on the security of coin flips when half the processors are faulty. In 18th ACM Symposium on the Theory of Computing, pages 364--369, 1986.]]

Digital Library

[12]

Y. Dodis, S. Halevi, and T. Rabin. A cryptographic solution to a game theoretic problem. In Advances in Cryptology --- CRYPTO 2000, volume 1880 of LNCS, pages 112--130. Springer-Verlag, 2000.]]

Digital Library

[13]

Y. Dodis and S. Micali. Parallel reducibility for information-theoretically secure computation. In Advances in Cryptology --- CRYPTO 2000, volume 1880 of LNCS, pages 74--92. Springer-Verlag, 2000.]]

Digital Library

[14]

S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. Technical Report 233, Technion, Haifa, February 1982. Subsequent version: CACM, 28(6) pp. 637-647, 1985.]]

Digital Library

[15]

P. Feldman and S. Micali. Byzantine agreement in constant expected time (and trusting no one). In Proc. 26th FOCS, pages 267--276. IEEE Computer Society, 1985.]]

[16]

J. A. Garay, P. MacKenzie, and K. Yang. Efficient and secure multi-party computation with faulty majority and complete fairness. Technical Report 9, Eprint, January 2004. http://eprint.iacr.org/2004/009.]]

[17]

D. Gerardi. Unmediated communication in games with complete and incomplete information. Journal of Economic Theory, to appear.]]

[18]

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proc. 19th STOC, pages 218--229. ACM, 1987.]]

Digital Library

[19]

S. Goldwasser and L. Levin. Fair computation of general functions in the presence of an immoral majority. In Proc. CRYPTO 90, pages 77--93. Springer Verlag, 1990.]]

Digital Library

[20]

M. Luby, S. Micali, and C. Rackoff. How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin. In FOCS, pages 11--21, 1983.]]

Digital Library

[21]

S. Micali and P. Rogaway. Secure computation. In J. Feigenbaum, editor, Proc. CRYPTO 91, pages 392--404. Springer, 1992. Lecture Notes in Computer Science No. 576.]]

Digital Library

[22]

D. Moreno and J. Wooders. Coalition-proof equilibrium. Games and Economic Behavior, 17:80--112, 1996.]]

[23]

H. Moulin and J. P. Vial. Strategically zero sum games. Internat. J. Game Theory, 7:201--221, 1978.]]

[24]

J. Nash. Non-cooperative games. Annals of Mathematics, 54:286--295, 1951.]]

[25]

T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proc. 21st STOC, pages 73--85. ACM, 1989.]]

Digital Library

[26]

I. Ray. Coalition-proof correlated equilibrium: A definition. Games and Economic Behavior, 17:56--79, 1996.]]

[27]

V. Teague. Selecting correlated random actions. In Proc. Financial Cryptography, 2004.]]

[28]

A. Urbano and J. E. Vila. Computational complexity and communication: Coordination in two-player games. Econometrica, 70(5):1893--1927, 2002.]]

[29]

A. C.-C. Yao. How to generate and exchange secrets. In Proc. 27th FOCS, pages 162--167. IEEE Computer Society, 1986.]]

Digital Library

Cited By

Mangipudi ELu DPsomas AKate A(2023)Collusion-Deterrent Threshold Information Escrow2023 IEEE 36th Computer Security Foundations Symposium (CSF)10.1109/CSF57540.2023.00010(584-599)Online publication date: Jul-2023
https://doi.org/10.1109/CSF57540.2023.00010
Kumaresan RRaghuraman SSealfon A(2023)Synchronizable Fair ExchangeTheory of Cryptography10.1007/978-3-031-48615-9_15(411-440)Online publication date: 27-Nov-2023
https://doi.org/10.1007/978-3-031-48615-9_15
Ciampi MLu YZikas V(2022)Collusion-Preserving Computation without a Mediator2022 IEEE 35th Computer Security Foundations Symposium (CSF)10.1109/CSF54842.2022.9919678(211-226)Online publication date: Aug-2022
https://doi.org/10.1109/CSF54842.2022.9919678
Show More Cited By

Index Terms

Completely fair SFE and coalition-safe cheap talk
1. Theory of computation

Recommendations

Computationally Secure Oblivious Transfer

We describe new computationally secure protocols of 1-out-of-N oblivious transfer, k-out-of-N oblivious transfer, and oblivious transfer with adaptive queries. The protocols are very efficient compared with solutions based on generic two-party ...
Secure Computation of the Median (and Other Elements of Specified Ranks)

We consider the problem of securely computing the kth-ranked element of the union of two or more large, confidential data sets. This is a fundamental question motivated by many practical contexts. For example, two competitive companies may wish to ...
MPC vs. SFE: perfect security in a unified corruption model
TCC'08: Proceedings of the 5th conference on Theory of cryptography

Secure function evaluation (SFE) allows a set of players to compute an arbitrary agreed function of their private inputs, even if an adversary may corrupt some of the players. Secure multi-party computation (MPC) is a generalization allowing to perform ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

July 2004

422 pages

ISBN:1581138024

DOI:10.1145/1011767

General Chair:
Soma Chaudhuri
Iowa State University
,
Program Chair:
Shay Kutten
Technion

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC04

Sponsor:

PODC04: Principles of Distributed Computing 2004

July 25 - 28, 2004

Newfoundland, St. John's, Canada

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
692
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mangipudi ELu DPsomas AKate A(2023)Collusion-Deterrent Threshold Information Escrow2023 IEEE 36th Computer Security Foundations Symposium (CSF)10.1109/CSF57540.2023.00010(584-599)Online publication date: Jul-2023
https://doi.org/10.1109/CSF57540.2023.00010
Kumaresan RRaghuraman SSealfon A(2023)Synchronizable Fair ExchangeTheory of Cryptography10.1007/978-3-031-48615-9_15(411-440)Online publication date: 27-Nov-2023
https://doi.org/10.1007/978-3-031-48615-9_15
Ciampi MLu YZikas V(2022)Collusion-Preserving Computation without a Mediator2022 IEEE 35th Computer Security Foundations Symposium (CSF)10.1109/CSF54842.2022.9919678(211-226)Online publication date: Aug-2022
https://doi.org/10.1109/CSF54842.2022.9919678
Seo M(2021)Fair and Secure Multi-Party Computation with Cheater DetectionCryptography10.3390/cryptography50300195:3(19)Online publication date: 12-Aug-2021
https://doi.org/10.3390/cryptography5030019
Couteau GRoscoe ARyan P(2021)Partially-Fair Computation from Timed-Release Encryption and Oblivious TransferInformation Security and Privacy10.1007/978-3-030-90567-5_17(330-349)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90567-5_17
Abraham IDolev DHalpern J(2019)Distributed Protocols for Leader ElectionACM Transactions on Economics and Computation10.1145/33037127:1(1-26)Online publication date: 14-Feb-2019
https://dl.acm.org/doi/10.1145/3303712
Halpern J(2016)Computer Science and Game TheoryThe New Palgrave Dictionary of Economics10.1057/978-1-349-95121-5_2133-1(1-14)Online publication date: 5-Dec-2016
https://doi.org/10.1057/978-1-349-95121-5_2133-1
Wang YLi TLiu QSun JLiu Z(2015)The impact of social cloud reputation and structure on rational computationJournal of High Speed Networks10.3233/JHS-15051921:3(181-194)Online publication date: 7-Aug-2015
https://doi.org/10.3233/JHS-150519
Wang YLi TQin HLi JGao WLiu ZXu Q(2015)A brief survey on secure multi-party computing in the presence of rational partiesJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-015-0299-26:6(807-824)Online publication date: 3-Jul-2015
https://doi.org/10.1007/s12652-015-0299-2
Afek YGinzberg YLandau Feibish SSulamy MHalldórsson MDolev S(2014)Distributed computing building blocks for rational agentsProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611481(406-415)Online publication date: 15-Jul-2014
https://dl.acm.org/doi/10.1145/2611462.2611481
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents