×

Fairness versus guaranteed output delivery in secure multiparty computation. (English) Zbl 1386.94067

Summary: In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed output delivery. In the case of no honest majority, fairness and guaranteed output delivery cannot always be obtained. Thus, protocols for secure multiparty computation are typically of two disparate types: protocols that assume an honest majority (and achieve all properties including fairness and guaranteed output delivery) and protocols that do not assume an honest majority (and achieve all properties except for fairness and guaranteed output delivery). In addition, in the two-party case, fairness and guaranteed output delivery are equivalent. As a result, the properties of fairness (which means that if corrupted parties receive output then so do the honest parties) and guaranteed output delivery (which means that corrupted parties cannot prevent the honest parties from receiving output in any case) have typically been considered to be the same.
In this paper, we initiate a study of the relation between fairness and guaranteed output delivery in secure multiparty computation. We show that in the multiparty setting these properties are distinct and proceed to study under what conditions fairness implies guaranteed output delivery (the opposite direction always holds). We also show the existence of non-trivial functions for which complete fairness is achievable (without an honest majority) but guaranteed output delivery is not, and the existence of non-trivial functions for which complete fairness and guaranteed output delivery are achievable. Our study sheds light on the role of broadcast in fairness and guaranteed output delivery and shows that these properties should sometimes be considered separately.
An extended abstract of this work appeared in [ASIACRYPT 2014, Lect. Notes Comput. Sci. 8874, 466–485 (2014; Zbl 1317.94099)].

MSC:

94A60 Cryptography

Citations:

Zbl 1317.94099
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Y. Aumann and Y. Lindell. Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries. Journal of Cryptology, 23(2):281-343, 2010. · Zbl 1181.94091 · doi:10.1007/s00145-009-9040-7
[2] G. Asharov. Towards Characterizing Complete Fairness in Secure Two-Party Computation. In Proceedings of the 11th Theory of Cryptography Conference, TCC 2014, pp. 291-316. · Zbl 1326.94070
[3] D. Beaver. Foundations of Secure Interactive Computing. In Advances in Cryptology-CRYPTO ’91, (1991), pp. 377-391. · Zbl 0789.68044
[4] R. Canetti. Security and Composition of Multiparty Cryptographic Protocols. Journal of Cryptology, 13(1):143-202, 2000. · Zbl 0957.68040 · doi:10.1007/s001459910006
[5] R. Cohen, Y. Lindell. Fairness versus Guaranteed Output Delivery in Secure Multiparty Computation. In Advances in Cryptology—ASIACRYPT 2014, part II, (2014), pp. 466-485. · Zbl 1317.94099
[6] R. Cleve. Limits on the Security of Coin Flips When Half the Processors are Faulty. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), (1986), pp. 364-369. · Zbl 0434.68031
[7] D. Dolev and H. R. Strong. Authenticated Algorithms for Byzantine Agreement. SIAM Journal on Computing, 12(4):656-666, 1983. · Zbl 0524.68021 · doi:10.1137/0212045
[8] M. Fitzi, D. Gottesman, M. Hirt, T. Holenstein, A. Smith. Detectable Byzantine Agreement Secure against Faulty Majorities. In Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC), (2002), pp. 118-126. · Zbl 1292.68029
[9] M. Fitzi, N. Gisin, M. Maurer, O. von Rotz. Unconditional Byzantine Agreement and Multi-party Computation Secure against Dishonest Minorities from Scratch. In Advances in Cryptology—EUROCRYPT 2002 (Springer, Berlin, 2002) pp. 482-501. · Zbl 1056.94501
[10] D. Gordon, C. Hazay, J. Katz, Y. Lindell. Complete Fairness in Secure Two-Party Computation. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), (2008), pp. 413-422. · Zbl 1231.94062
[11] D. Gordon, J. Katz. Complete Fairness in Multi-party Computation without an Honest Majority. In Proceedings of the 6th Theory of Cryptography Conference, TCC 2009, (2009), pp. 19-35. · Zbl 1213.94104
[12] S. Goldwasser, L.A. Levin. Fair Computation of General Functions in Presence of Immoral Majority. In Advances in Cryptology—CRYPTO ’90 (1990), pp. 77-93. · Zbl 0800.68459
[13] S. Goldwasser and Y. Lindell. Secure Multi-Party Computation without Agreement. Journal of Cryptology, 18(3):247-287, 2005. · Zbl 1102.68472 · doi:10.1007/s00145-005-0319-z
[14] O. Goldreich, S. Micali, A. Wigderson. How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), (1987), pp. 218-229. · Zbl 0524.68021
[15] O. Goldreich. The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press, 2004. · Zbl 1068.94011 · doi:10.1017/CBO9780511721656
[16] J. Kilian. A General Completeness Theorem for Two-Party Games. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC) (1991), pp. 553-560.
[17] L. Lamport, R. E. Shostak, and M. C. Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401, 1982. · Zbl 0483.68021 · doi:10.1145/357172.357176
[18] S. Micali, P. Rogaway. Secure Computation (Abstract). In Advances in Cryptology - CRYPTO ’91 (1991), pp. 392-404.
[19] M. C. Pease, R. E. Shostak, and L. Lamport. Reaching Agreement in the Presence of Faults. Journal of the ACM, 27(2):228-234, 1980. · Zbl 0434.68031 · doi:10.1145/322186.322188
[20] B. Pfitzmann, M. Waidner. Unconditional Byzantine Agreement for any Number of Faulty Processors. In Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS) (1992), pp. 339-350. · Zbl 1493.68036
[21] T. Rabin, M. Ben-Or. Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract). In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS) (1989), pp. 73-85.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.