Abstract
A computation scheme among n parties is fair if no party obtains the computation result unless all other \(n-1\) parties obtain the same result. A fair computation scheme is optimistic if n honest parties can obtain the computation result without resorting to a trusted third party. We prove, for the first time, a tight lower-bound on the message complexity of optimistic fair computation for n parties among which \(n-1\) can be malicious in an asynchronous network. We do so by relating the optimal message complexity of optimistic fair computation to the length of the shortest permutation sequence in combinatorics.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Newey [6] (and then many others [7–11]) studied the length \(\ell \) of the shortest permutation sequence. Although Newey [6] showed that \(\ell = 3\) for \(n = 2\), and \(\ell = n^2 - 2n + 4\) for \(3\le n \le 7\), the exact \(\ell \) for \(n\ge 8\) is still considered as an open problem [7, 8]. Up until now, the best upper-bound is \(\lceil n^2 - \frac{7}{3} n + \frac{19}{3} \rceil \) for \(n\ge 7\) [8], while a lower-bound of \(\ell \) is of the form \(n^2 - cn^{7/4} + \epsilon \) for some constant c and some \(\epsilon > 0\) [9].
- 2.
Hereafter, when we say that a probability is negligible, we mean that the probability is a negligible function g(s) of the security parameter s; i.e., \(\forall c\in \mathbb {N}\), \(\exists C\in \mathbb {N}\) such that \(\forall s > C\), \(g(s) < \frac{1}{s^c}\).
- 3.
We consider deterministic protocols here (for Compute and Stop). In this paper, deterministic protocols consists of two classes of protocols: D1 and D2. In any protocol of D1, each party runs a deterministic algorithm and sends deterministic messages; and we define D2 based on D1: for any protocol \(\pi _1\) in class D1, we can create a protocol \(\pi _2\) in class D2 such that \(\pi _1\) and \(\pi _2\) are the same except for the message contents of \(\pi _2\) which can be randomized.
- 4.
The original definition in [2] is ambiguous when all parties are honest: (1) if an algorithm \(\mathcal {A}\) delays every message, then to ensure termination, every honest party should output \(\bot \) at some point in time; however, by the original definition, all honest parties output z, except with negligible probability, which yields a contradiction; and (2) if in a protocol, all parties send no message and only outputs \(\bot \), then this protocol also matches the ideal process, which however is a trivial protocol.
- 5.
\(\mathcal {A}\) also plays the role of the asynchronous network as defined in Sect. 2.1.
- 6.
In the ideal process, \(\mathcal {S}\) sees \(x_{d_1}, x_{d_2}, \ldots , x_{d_e}\), may change \(a_{d_1}, a_{d_2}, \ldots , a_{d_e}\) and also sees \(m_{d_1}, m_{d_2}, \ldots , m_{d_e}\) but \(\mathcal {S}\) cannot see other messages from or to U, or U’s internal state (which makes U universally trusted and the process ideal).
- 7.
For example, \(f=x_1\cdot x_2\cdots x_n\) is not in \(\mathcal {C}\) (since if one of the values is 0, the output is 0 with probability 1) while \(f=x_1+x_2+\cdots +x_n\) is.
- 8.
We also assume that for \(i\in \{1,2,\ldots ,n\}\), given \(a_i\), any computationally-bounded algorithm outputs \(x_i\) with negligible probability, and given \((a_i, x_i)\) such that \((a_i, x_i)\in R_i\), any computationally-bounded algorithm outputs \(y_i, y_i\ne x_i\) such that \((a_i, y_i)\in R_i\) with negligible probability.
- 9.
In the application of fair exchange of digital signatures, \(R_i\) is an homomorphism \(\theta \) depending on the given digital signature scheme [1]; each of the first n messages of \(\pi \) is appended with an image of \(\theta \) such that its pre-image produces a correct signature.
- 10.
The main difference is that contract signing outputs a proof which binds a contract agreed in advance, while computation usually does not require such binding.
- 11.
Although [14] proved that the resulting protocol needs at least \(\ell + 2n -3\) messages in an optimistic execution, the number of messages exchanged during every optimistic execution is actually strictly larger than \(\ell + 2n -3\) for \(n\ge 3\), and is thus not optimal.
References
Asokan, N., Shoup, V., Waidner, M.: Optimistic fair exchange of digital signatures. Sel. Areas Commun. IEEE J. 18(4), 593–610 (2000)
Cachin, C., Camenisch, J.L.: Optimistic fair secure computation. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 93–111. Springer, Heidelberg (2000)
Cleve, R.: Limits on the security of coin flips when half the processors are faulty. In: STOC 1986, pp. 364–369 (1986)
Micali, S.: Simple and fast optimistic protocols for fair electronic exchange. In: PODC (2003)
Knuth, D.E.: Open problems with a computational flavor, mimeographed notes for a seminar on combinatorics (1971)
Newey, M.C.: Notes on a problem involving permutations as subsequences. Technical Report (1973)
Zălinescu, E.: Shorter strings containing all k-element permutations. Inf. Process. Lett. 111(12), 605–608 (2011)
Radomirović, S.: A construction of short sequences containing all permutations of a set as subsequences. Electron. J. Comb. 19(4) (2012). Paper 31
Kleitman, D., Kwiatkowski, D.: A lower bound on the length of a sequence containing all permutations as subsequences. J. Comb. Theor. Ser. A 21(2), 129–136 (1976)
Adleman, L.: Short permutation strings. Discrete Math. 10(2), 197–200 (1974)
Koutas, P., Hu, T.: Shortest string containing all permutations. Discrete Math. 11(2), 125–132 (1975)
Camenisch, J.L., Damgård, I.B.: Verifiable encryption, group encryption, and their applications to separable group signatures and signature sharing schemes. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 331–345. Springer, Heidelberg (2000)
Mauw, S., Radomirović, S., Dashti, M.: Minimal message complexity of asynchronous multi-party contract signing. In: CSF (2009)
Kordy, B., Radomirović, S.: Constructing optimistic multi-party contract signing protocols. In: CSF (2012)
Mauw, S., Radomirović, S.: Generalizing multi-party contract signing. In: Focardi, R., Myers, A. (eds.) POST 2015. LNCS, vol. 9036, pp. 156–175. Springer, Heidelberg (2015)
Pfitzmann, B., Schunter, M., Waidner, M.: Optimal efficiency of optimistic contract signing. In: PODC 1998, pp. 113–122 (1998)
Schunter, M.: Optimistic fair exchange. Ph.D. dissertation, Universität des Saarlandes (2000). http://scidok.sulb.uni-saarland.de/volltexte/2004/233
Dashti, M.T.: Efficiency of optimistic fair exchange using trusted devices. ACM Trans. Auton. Adapt. Syst. 7(1), 3:1–3:18 (2012)
Schnorr, C.: Efficient signature generation by smart cards. J. Cryptology 4(3), 161–174 (1991)
Kravitz, D.: Digital signature algorithm. US Patent 5,231,668 (1993)
Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Ong, H., Schnorr, C.-P.: Fast signature generation with a fiat shamir-like scheme. In: Damgård, I.B. (ed.) EUROCRYPT 1990. LNCS, vol. 473, pp. 432–440. Springer, Heidelberg (1991)
Guillou, L.C., Quisquater, J.-J.: A “paradoxical” indentity-based signature scheme resulting from zero-knowledge. In: Goldwasser, S. (ed.) Advances in Cryptology — CRYPTO’88. LNCS, vol. 403, pp. 216–231. Springer, Heidelberg (2000)
Guerraoui, R., Wang, J.: Optimal fair computation. Technical Report (2016). http://infoscience.epfl.ch/record/219171
Oded, G.: Foundations of Cryptography. Basic Applications, vol. 2. Cambridge University Press, New York (2009)
Dierks, T.: The transport layer security (tls) protocol version 1.2 (2008)
Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptology 13(1), 143–202 (2000)
Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)
Yao, A.C.: Theory and application of trapdoor functions. In: SFCS 1982, pp. 80–91 (1982)
Gordon, S.D., Katz, J.: Complete fairness in multi-party computation without an honest majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 19–35. Springer, Heidelberg (2009)
Gordon, S.D., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. J. ACM
Menezes, A.J., Vanstone, S.A., Oorschot, P.C.V.: Handbook of Applied Cryptography. CRC Press Inc., Boca Raton (1996)
I. 9594–8. Information technology - open systems interconnection - the directory: Authentication framework (1995). (equivalent to ITU-T Recommendation X.509, 1993)
Ateniese, G.: Efficient verifiable encryption (and fair exchange) of digital signatures. In: CCS 1999, pp. 138–146 (1999)
Alaraj, A.M.: Simple and efficient contract signing protocol. CoRR, vol. abs/1204.1646 (2012). http://arxiv.org/abs/1204.1646
Guerraoui, R., Rodrigues, L.: Introduction to Reliable Distributed Programming. Springer, New York (2006)
Acknowledgements
We are very grateful to the second author of [16] for the time devoted to understanding our argument and for his fairplay in recognizing the mistake. This work has been supported in part by the European ERC Grant 339539 - AOC.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guerraoui, R., Wang, J. (2016). Optimal Fair Computation. In: Gavoille, C., Ilcinkas, D. (eds) Distributed Computing. DISC 2016. Lecture Notes in Computer Science(), vol 9888. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53426-7_11
Download citation
DOI: https://doi.org/10.1007/978-3-662-53426-7_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-53425-0
Online ISBN: 978-3-662-53426-7
eBook Packages: Computer ScienceComputer Science (R0)