Abstract
We introduce the notion of resource-fair protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to previously proposed definitions related to fairness, our definition follows the standard simulation paradigm and enjoys strong composability properties. In particular, our definition is similar to the security definition in the universal composability (UC) framework, but works in a model that allows any party to request additional resources from the environment to deal with dishonest parties that may prematurely abort.
In this model we specify the ideally fair functionality as allowing parties to “invest resources” in return for outputs, but in such an event offering all other parties a fair deal. (The formulation of fair dealings is kept independent of any particular functionality, by defining it using a “wrapper.”) Thus, by relaxing the notion of fairness, we avoid a well-known impossibility result for fair multi-party computation with corrupted majority; in particular, our definition admits constructions that tolerate arbitrary number of corruptions. We also show that, as in the UC framework, protocols in our framework may be arbitrarily and concurrently composed.
Turning to constructions, we define a “commit-prove-fair-open” functionality and design an efficient resource-fair protocol that securely realizes it, using a new variant of a cryptographic primitive known as “time-lines.” With (the fairly wrapped version of) this functionality we show that some of the existing secure multi-party computation protocols can be easily transformed into resource-fair protocols while preserving their security.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
L. Adleman, K. Kompella, Using smoothness to achieve parallelism, in Proceedings of the 20th ACM Symposium on the Theory of Computing (1988), pp. 528–538
N. Asokan, V. Shoup, M. Waidner, Optimistic fair exchange of digital signatures (extended abstract), in EUROCRYPT 1998 (1998), pp. 591–606
M. Backes, B. Pfitzmann, M. Waidner, A general composition theorem for secure reactive systems, in 1st Theory of Cryptography Conference (TCC). LNCS, vol. 2951 (Springer, Berlin, 2004), pp. 336–354
D. Beaver, S. Goldwasser, Multiparty computation with faulty majority, in 30th FOCS (1990), pp. 503–513
J. Benaloh, M. de Mare, One-way accumulators: a decentralized alternative to digital signatures, in EUROCRYPT 1993. LNCS, vol. 765 (Springer, Berlin, 1994), pp. 274–285
M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in 20th STOC (1988), pp. 1–10
M. Blum, How to exchange (secret) keys. ACM Trans. Comput. Syst. 1(2), 175–193 (1983)
D. Boneh, The decision Diffie–Hellman problem, in Proceedings of the Third Algorithmic Number Theory Symposium. LNCS, vol. 1423 (Springer, Berlin, 1998), pp. 48–63
D. Boneh, M. Naor, Timed commitments (extended abstract), in Advances in Cryptology—CRYPTO’00. LNCS, vol. 1880 (Springer, Berlin, 2000), pp. 236–254
C. Cachin, J. Camenisch, Optimistic fair secure computation, in Advances in Cryptology—CRYPTO’00. LNCS, vol. 1880 (Springer, Berlin, 2000), pp. 93–111
R. Canetti, Security and composition of multiparty cryptographic protocols. J. Cryptol. 13(1), 143–202 (2000)
R. Canetti, Universally composable security: A new paradigm for cryptographic protocols. Electronic Colloquium on Computational Complexity (ECCC) TR01-016 (2001). Previous version “A unified framework for analyzing security of protocols” available at the ECCC archive TR01-016. Extended abstract in FOCS (2001)
R. Canetti, Universally composable security: A new paradigm for cryptographic protocols. Cryptology ePrint Archive, Report 2000/067 (2005). Revised version of [15]
R. Canetti, M. Fischlin, Universally composable commitments, in CRYPTO 2001. LNCS, vol. 2139 (Springer, Berlin, 2001), pp. 19–40
R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai, Universally composable two-party and multi-party secure computation, in 34th ACM Symposium on the Theory of Computing (2002)
D. Chaum, C. Crépeau, I. Damgård, Multiparty unconditionally secure protocols, in 20th STOC (1988), pp. 11–19
B. Chor, S. Goldwasser, S. Micali, B. Awerbuch, Verifiable secret sharing and achieving simultaneity in the presence of faults, in Proc. 26th Annual Symposium on Foundations of Computer Science (1985), pp. 383–395
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) (1986), pp. 364–369
R. Cramer, Modular design of secure yet practical cryptographic protocols. Ph.D. Thesis, CWI and University of Amsterdam (1997)
R. Cramer, I. Damgård, B. Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocols, in Advances in Cryptology—CRYPTO’94. LNCS, vol. 839 (Springer, Berlin, 1994), pp. 174–187
R. Cramer, I. Damgård, J. Nielsen, Multiparty computation from threshold homomorphic encryption, in Advances in Cryptology—EuroCrypt 2001 Proceedings. LNCS, vol. 2045 (Springer, Berlin, 2001), pp. 280–300
I. Damgård, Practical and provably secure release of a secret and exchange of signatures. J. Cryptol. 8(4), 201–222 (1995)
I. Damgård, M. Jurik, Efficient protocols based probabilistic encryptions using composite degree residue classes, in Research Series RS-00-5, BRICS, Department of Computer Science, University of Aarhus (2000)
I. Damgård, J. Nielsen, Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor, in Advances in Cryptology—CRYPTO’02 (2002)
I. Damgård, J. Nielsen, Universally composable efficient multiparty computation from threshold homomorphic encryption, in Advances in Cryptology—CRYPTO’03 (2003)
S. Even, O. Goldreich, A. Lempel, A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)
M. Fitzi, J. Garay, U. Maurer, R. Ostrovsky, Minimal complete primitives for secure multi-party computation, in Advances in Cryptology—CRYPTO’01 (2001), pp. 80–100
M. Fitzi, D. Gottesman, M. Hirt, T. Holenstein, A. Smith, Detectable byzantine agreement tolerating faulty majorities (from scratch), in 21st PODC (2002), pp. 118–126
P. Fouque, G. Poupard, J. Stern, Sharing decryption in the context of voting or lotteries, in Proceedings of Financial Crypto 2000 (2000)
Z. Galil, S. Haber, M. Yung, Cryptographic computation secure fault-tolerant protocols and the public-key model, in Advances in Cryptology—CRYPTO’87 (1988), pp. 135–155
J. Garay, M. Jakobsson, Timed release of standard digital signatures, in Financial Cryptography’02. LNCS, vol. 2357 (Springer, Berlin, 2002), pp. 168–182
J. Garay, C. Pomerance, Timed fair exchange of standard signatures, in Financial Cryptography 2003. LNCS, vol. 2742 (Springer, Berlin, 2003), pp. 190–207
J. Garay, P. MacKenzie, K. Yang, Strengthening zero-knowledge protocols using signatures. J. Cryptol. 19(2), 169–209 (2006). Preliminary version in Advances in Cryptology—Eurocrypt 2003, Warsaw, Poland. LNCS, vol. 2656 (Springer, Berlin, 2003), pp. 177–194
J. Garay, P. MacKenzie, K. Yang, Efficient and secure multi-party computation with faulty majority and complete fairness. Cryptology ePrint Archive, http://eprint.iacr.org/2004/019
O. Goldreich, The Foundations of Cryptography, vol. 2 (Cambridge University Press, Cambridge, 2004)
O. Goldreich, S. Micali, A. Wigderson, How to play any mental game—a completeness theorem for protocols with honest majority, in 19th ACM Symposium on the Theory of Computing (1987), pp. 218–229
S. Goldwasser, L. Levin, Fair computation of general functions in presence of immoral majority, in CRYPTO’90 (Springer, Berlin, 1991), pp. 77–93
S. Goldwasser, Y. Lindell, Secure computation without agreement. J. Cryptol. 18(3), 247–287 (2005)
D. Gordon, J. Katz, Partial fairness in secure two-party computation, in Advances in Cryptology—Eurocrypt’10. LNCS, vol. 6110 (Springer, Berlin, 2010), pp. 157–176
D. Gordon, C. Hazay, J. Katz, Y. Lindell, Complete fairness in secure two-party computation, in Proc. 40th Annual ACM Symposium on the Theory of Computing (2008), pp. 413–422
D. Gordon, Y. Ishai, T. Moran, R. Ostrovsky, A. Sahai, in Proc. 7th Theory of Cryptography Conference (TCC) (2010), pp. 91–108
D. Hofheinz, J. Müller-Quade, A synchronous model for multi-party computation and incompleteness of oblivious transfer, in Proc. Workshop on Foundations of Computer Security (2004)
J. Kilian, Founding cryptography on oblivious transfer, in Proc. 20th Annual ACM Symposium on the Theory of Computing (1988), pp. 20–31
J. Kilian, More general completeness theorems for secure two-party computation, in Proc. 32nd Annual ACM Symposium on the Theory of Computing (2000), pp. 316–324
M. Lepinski, S. Micali, C. Peikert, A. Shelat, Completely fair SFE and coalition-safe cheap talk, in 23rd PODC (2004), pp. 1–10
Y. Lindell, General composition and universal composability in secure multi-party computation, in FOCS 2003
P. MacKenzie, K. Yang, On simulation sound trapdoor commitments. Manuscript
T. Moran, M. Naor, G. Segev, An optimally fair coin toss: Cleve’s bound is tight, in Proc. 6th Theory of Cryptography Conference (2009), pp. 1–18
J.B. Nielsen, On protocol security in the cryptography model. Ph.D. Thesis. Aarhus University (2003)
P. Paillier, Public-key cryptosystems based on composite degree residue classes, in Advances in Cryptology–Eurocrypt’99 (1999), pp. 223–238
T.P. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, in Advances in Cryptology—CRYPTO’91. LNCS, vol. 576 (Springer, Berlin, 1991), pp. 129–140
B. Pfitzmann, M. Waidner, Composition and integrity preservation of secure reactive systems, in ACM Conference on Computer and Communications Security (CSS) (2000), pp. 245–254
B. Pinkas, Fair secure two-party computation, in Eurocrypt 2003 (2003), pp. 87–105
T. Rabin, M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, in 21st STOC (1989), pp. 73–85
V. Shoup, A Computational Introduction to Number Theory and Algebra. Preliminary book, available at http://shoup.net/ntb/
J. Sorenson, A sublinear-time parallel algorithm for integer modular exponentiation. Available from http://citeseer.nj.nec.com/sorenson99sublineartime.html
A. Yao, Protocols for secure computation, in FOCS 1982 (1982), pp. 160–164
A. Yao, How to generate and exchange secrets, in FOCS 1986 (1986), pp. 162–167
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Ran Canetti
A preliminary version of this paper appeared in Proc. 3th Theory of Cryptography Conference (TCC’06).
Rights and permissions
About this article
Cite this article
Garay, J.A., MacKenzie, P., Prabhakaran, M. et al. Resource Fairness and Composability of Cryptographic Protocols. J Cryptol 24, 615–658 (2011). https://doi.org/10.1007/s00145-010-9080-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-010-9080-z