Abstract
Prior approaches [14, 15] to building collusion-free protocols require exotic channels. By taking a conceptually new approach, we are able to use a more digitally-friendly communication channel to construct protocols that achieve a stronger collusion-free property.
We consider a communication channel which can filter and rerandomize message traffic. We then provide a new security definition that captures collusion-freeness in this new setting; our new setting even allows for the mediator to be corrupted in which case the security gracefully fails to providing standard privacy and correctness. This stronger notion makes the property useful in more settings.
To illustrate feasibility, we construct a commitment scheme and a zero-knowledge proof of knowledge that meet our definition in its two variations.
Chapter PDF
Similar content being viewed by others
References
Alparone, M., Persiano, G.: Staganography-free implementation of yao’s protocol. Technical report (unpublished, 2006)
Aumann, R.J.: Subjectivity and Correlation in Randomized Strategies. Journal of Mathematical Economics 1(1), 67–96 (1974)
Barak, B., Canetti, R., Lindell, Y., Pass, R., Rabin, T.: Secure computation without authentication. In: CRYPTO 2006. LNCS, vol. 4622, pp. 361–377. Springer, Heidelberg (2005)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation. In: STOC 1988: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 1–10. ACM, New York (1988)
Boneh, D., Golle, P.: Almost Entirely Correct Mixing with Applications to Voting. In: CCS 2002, pp. 68–77 (2002)
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: Proc. 42nd FOCS, pp. 136–145 (2001)
Chaum, D., Ryan, P., Schneider, S.: A Practical Voter-Verifiable Election Scheme. In: de Capitani di Vimercati, S., Syverson, P.F., Gollmann, D. (eds.) ESORICS 2005. LNCS, vol. 3679, pp. 118–139. Springer, Heidelberg (2005)
Cramer, R., Gennaro, R., Schoenmakers, B.: A Secure and Optimally Efficient Multi-Authority Election Scheme. In: EUROCRYPT 2006. LNCS, pp. 103–118. Springer, Heidelberg (2006)
Cramton, P., Schwartz, J.: Collusive bidding in the fcc spectrum auctions. Technical Report 02collude, University of Maryland, Department of Economics (December 2002), http://ideas.repec.org/p/pcc/pccumd/02collude.html
Dwork, C., Naor, M., Sahai, A.: Concurrent Zero-Knowledge. In: 30th ACM Symposium on Theory of Computing (STOC 1998), pp. 409–418. ACM, New York (1998)
Goldreich, O., Micali, S., Wigderson, A.: How to Play Any Mental Game. In: STOC 1987: Proceedings of the nineteenth annual ACM conference on Theory of computing, pp. 218–229. ACM Press, New York (1987)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that Yield Nothing but their Validity or all Languages in NP have Zero-Knowledge Proof Systems. J. ACM 38(3), 690–728 (1991)
Izmalkov, S., Lepinski, M., Micali, S.: Verifiably secure devices. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 273–301. Springer, Heidelberg (2008)
Izmalkov, S., Micali, S., Lepinski, M.: Rational Secure Computation and Ideal Mechanism Design. In: FOCS 2005: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC, USA, pp. 585–595. IEEE Computer Society, Los Alamitos (2005)
Lepinksi, M., Micali, S., Shelat, A.: Collusion-Free Protocols. In: STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 543–552. ACM, New York (2005)
Lepinski, M., Micali, S., Peikert, C., Shelat, A.: Completely Fair SFE and Coalition-Safe Cheap Talk. In: PODC 2004: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pp. 1–10. ACM Press, New York (2004)
Micciancio, D., Petrank, E.: Simulatable Commitments and Efficient Concurrent Zero-Knowledge. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 140–159. Springer, Heidelberg (2003)
Neff, C.: A Verifiable Secret Shuffle and its Application to e-Voting. In: CCS 2001, pp. 116–125 (2001)
Prabhakaran, M., Rosen, A., Sahai, A.: Concurrent Zero-Knowledge with Logarithmic Round Complexity. In: 43th IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp. 366–375 (2002)
Simmons, G.J.: The prisoners’ problem and the subliminal channel. In: CRYPTO 1983, pp. 51–67 (1983)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alwen, J., Shelat, A., Visconti, I. (2008). Collusion-Free Protocols in the Mediated Model. In: Wagner, D. (eds) Advances in Cryptology – CRYPTO 2008. CRYPTO 2008. Lecture Notes in Computer Science, vol 5157. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85174-5_28
Download citation
DOI: https://doi.org/10.1007/978-3-540-85174-5_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85173-8
Online ISBN: 978-3-540-85174-5
eBook Packages: Computer ScienceComputer Science (R0)