Abstract
We study various classical secure computation problems in the context of fairness, and relate them with each other. We also systematically study fair sampling problems (i.e., inputless functionalities) and discover three levels of complexity for them.
Our results include the following:
-
Fair exchange cannot be securely reduced to the problem of fair cointossing by an r-round protocol, except with an error that is \(\Omega(\frac{1}{r})\).
-
Finite fair sampling problems with rational probabilities can all be reduced to fair coin-tossing and unfair 2-party computation (or equivalently, under computational assumptions). Thus, for this class of functionalities, fair coin-tossing is complete.
-
Only sampling problems which have fair protocols without any fair setup are the trivial ones in which the two parties can sample their outputs independently.Others all have an \(\Omega(\frac{1}{r})\) error, roughly matching an upperbound for fair sampling from [21].
-
We study communication-less protocols for sampling, given another sampling problem as setup, since such protocols are inherently fair. We use spectral graph theoretic tools to show that it is impossible to reduce a sampling problem with common information (like fair cointossing) to a sampling problem without (like “noisy” coin-tossing, which has a small probability of disagreement).
The last result above is a slightly sharper version of a classical result by Witsenhausen from 1975. Our proof reveals the connection between the tool used by Witsenhausen, namely “maximal correlation,” and spectral graph theoretic tools like Cheeger inequality.
Research supported in part by NSF grants 1228856 and 0747027.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Asharov, G., Lindell, Y., Rabin, T.: A full characterization of functions that imply fair coin tossing and ramifications to fairness. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 243–262. Springer, Heidelberg (2013)
Beimel, A., Lindell, Y., Omri, E., Orlov, I.: 1/p-secure multiparty computation without honest majority and the best of both worlds. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 277–296. Springer, Heidelberg (2011)
Beimel, A., Omri, E., Orlov, I.: Protocols for multiparty coin toss with dishonest majority. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 538–557. Springer, Heidelberg (2010)
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. Cryptology ePrint Archive, Report 2000/067 (2005) (revised version of [?]. 7)
Cheeger, J.: A lower bound for the smallest eigenvalue of the laplacian. Problems in analysis 625, 195–199 (1970)
Chung, F.R.K.: Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92). American Mathematical Society (1996)
Chung, F.R.K., Tetali, P.: Isoperimetric inequalities for cartesian products of graphs. Combinatorics, Probability & Computing 7(2), 141–148 (1998)
Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: Hartmanis, J. (ed.) STOC, pp. 364–369. ACM (1986)
Cleve, R., Impagliazzo, R.: Martingales, collective coin flipping and discrete control processes (1993) (manuscript), http://www.cpsc.ucalgary.ca/~cleve/pubs/martingales.ps
Even, S., Yacobi, Y.: Relations among public key signature systems. Technical Report 175, Technion, Haifa, Israel (1980)
Gács, P., Körner, J.: Common information is far less than mutual information. Problems of Control and Information Theory 2(2), 149–162 (1973)
Gebelein, H.: Das statistische problem der korrelation als variations und eigenwertproblem und sein zusammenhang mit der ausgleichungsrechnung. Zeitschrift für angew. Math. und Mech. 21, 364–379 (1941)
Gordon, S.D., Katz, J.: Partial fairness in secure two-party computation. Journal of Cryptology 25(1), 14–40 (2012); Preliminary version in Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 157–176. Springer, Heidelberg (2010)
Gordon, S.D., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. J. ACM 58(6), 24:1–24:37 (2011); Preliminary version in STOC 2008
Gordon, D., Ishai, Y., Moran, T., Ostrovsky, R., Sahai, A.: On complete primitives for fairness. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 91–108. Springer, Heidelberg (2010)
Gray, R.M., Wyner, A.D.: Source coding for a simple network. Bell System Technical Journal 53, 1681–1721 (1974)
Ishai, Y., Ostrovsky, R., Seyalioglu, H.: Identifying cheaters without an honest majority. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 21–38. Springer, Heidelberg (2012)
Kilian, J.: More general completeness theorems for secure two-party computation. In: Yao, F.F., Luks, E.M. (eds.) STOC, pp. 316–324. ACM (2000)
Kumar, G.: Binary renyi correlation: A simpler proof of Witsenhausen’s result and a tighter upper bound (2010) (manuscript), http://www.stanford.edu/~gowthamr/research/binary_renyi_correlation.pdf
Maji, H.K., Ouppaphan, P., Prabhakaran, M., Rosulek, M.: Exploring the limits of common coins using frontier analysis of protocols. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 486–503. Springer, Heidelberg (2011)
Moran, T., Naor, M., Segev, G.: An optimally fair coin toss. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 1–18. Springer, Heidelberg (2009)
Rényi, A.: On measures of dependence. Acta Math. Hung. 10, 441–451 (1959)
Witsenhausen, H.S.: On sequences of pairs of dependent random variables. SIAM Journal of Applied Mathematics 28, 100–113 (1975)
Wyner, A.D.: The common information of two dependent random variables. IEEE Transactions on Information Theory 21(2), 163–179 (1975)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 International Association for Cryptologic Research
About this paper
Cite this paper
Agrawal, S., Prabhakaran, M. (2013). On Fair Exchange, Fair Coins and Fair Sampling. In: Canetti, R., Garay, J.A. (eds) Advances in Cryptology – CRYPTO 2013. CRYPTO 2013. Lecture Notes in Computer Science, vol 8042. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40041-4_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-40041-4_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40040-7
Online ISBN: 978-3-642-40041-4
eBook Packages: Computer ScienceComputer Science (R0)