Collusion-free protocols

ABSTRACT

Secure protocols attempt to minimize the injuries to privacy and correctness inflicted by malicious participants who collude during run-time. They do not, however, prevent malicious parties from colluding and coordinating their actions in the first place!Eliminating such collusion of malicious parties during the execution of a protocol is an important and exciting direction for research in Cryptography. We contribute the first general result in this direction: (1) We provide a rigorous definition of what a collusion-free protocol is; and (2) We prove that, under standard physical and computational assumptions ---i.e., plain envelopes and trapdoor permutations---collusion-free protocols exist for all finite protocol tasks with publicly observable actions. (Note that such tasks are allowed to have secret global state, and thus include Poker, Bridge, and other such games.Our solution is tight in the sense that, for a collusion-free protocol to exist, each of (a) the finiteness of the game of interest, (b) the public observability of its actions, and (c) the use of some type of physically private channel is provably essential.

REFERENCES

• 1: M. Backes and C. Cachin. Public-key steganography with active attacks. In TCC '05, 2005.
• 2: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 3: Manuel Blum , Alfredo De Santis , Silvio Micali , Giuseppe Persiano, Noninteractive zero-knowledge, SIAM Journal on Computing, v.20 n.6, p.1084-1118, Dec. 1991 [doi>10.1137/0220068]
• 4: Christian Cachin, An Information-Theoretic Model for Steganography, Proceedings of the Second International Workshop on Information Hiding, p.306-318, April 14-17, 1998
• 5: R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001
• 6: Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238015]
• 7: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 8: Claude Crepeau, A secure poker protocol that minimizes the effect of player coalitions, Lecture notes in computer sciences; 218 on Advances in cryptology---CRYPTO 85, p.73-86, June 1986, Santa Barbara, California, United States
• 9: Yevgeniy Dodis , Silvio Micali, Parallel Reducibility for Information-Theoretically Secure Computation, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.74-92, August 20-24, 2000
• 10: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 11: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 12: S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Science, 28(2), 1984.
• 13: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 14: S. Katzenbeisser and F. A. P. Petitcolas. Defining security in steganographic system. In Security and Watermarking of Multimedia Contents IV, pages 260--268, 2002.
• 15: M. Lepinski, S. Micali, and abhi shelat. Fair-zero knowledge. In TCC 2005, pages 245--263, 2005.
• 16: Nicholas J. Hopper , John Langford , Luis von Ahn, Provably Secure Steganography, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.77-92, August 18-22, 2002
• 17: A. Shamir, R. Rivest, and L. Adleman. Mental poker. Technical report, MIT, 1978.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

General Terms:
Security, Theory

Keywords:
secure function evaluation, steganography