Covert two-party computation

ABSTRACT

We introduce covert two-party computation, a stronger notion of security than standard secure two-party computation. Like standard secure two-party computation, covert two-party computation allows Alice and Bob, with secret inputs xA and xB respectively, to compute a function f(xA,xB) without leaking any additional information about their inputs. In addition, covert two-party computation guarantees that even the existence of a computation is hidden from all protocol participants unless the value of the function mandates otherwise. This allows the construction of protocols that return f(xA,xB) only when it equals a certain value of interest (such as "Yes, we are romantically interested in each other") but for which neither party can determine whether the other even ran the protocol whenever f(xA,xB) is not a value of interest. Since existing techniques for secure function evaluation always reveal that both parties participate in the computation, covert computation requires the introduction of new techniques based on provably secure steganography. We introduce security definitions for covert two-party computation and show that this surprising notion can be achieved by a protocol given the Decisional Diffie-Hellman assumption in the "honest but curious" model. Using this protocol as a subroutine, we present another protocol which is fair and secure against malicious adversaries in the Random Oracle Model --- unlike most other protocols against malicious adversaries, this protocol does not rely on zero-knowledge proofs (or similar cut-and-choose techniques), because they inherently reveal that a computation took place. We remark that all our protocols are of comparable efficiency to protocols for standard secure two-party computation.

REFERENCES

• 1: G. Aggarwal, N. Mishra and B. Pinkas. Secure computation of the k'th-ranked element. In: Advances in Cryptology - Proceedings of Eurocrypt '04, pages 40--55, 2004.
• 2: L. von Ahn and N. Hopper. Public-Key Steganography. In: Advances in Cryptology -- Proceedings of Eurocrypt '04, pages 323--341, 2004.
• 3: M. Backes and C. Cachin. Public-Key Steganography with Active Attacks. in Theory of Cryptography Conference (TCC), pages 210--226, 2005.
• 4: M. Bellare, A. Boldyreva, and A. Palacio An Uninstantiable Random-Oracle-Model Scheme for a Hybrid-Encryption Problem. In: Advances in Cryptology --- Eurocrypt 2004, pages 171--188, 2004.
• 5: Mihir Bellare , Silvio Micali, Non-interactive oblivious transfer and applications, Proceedings on Advances in cryptology, p.547-557, July 1989, Santa Barbara, California, United States
• 6: Ernest F. Brickell , David Chaum , Ivan Damgård , Jeroen van de Graaf, Gradual and Verifiable Release of a Secret, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.156-166, August 16-20, 1987
• 7: Christian Cachin, An Information-Theoretic Model for Steganography, Proceedings of the Second International Workshop on Information Hiding, p.306-318, April 14-17, 1998
• 8: Ran Canetti , Oded Goldreich , Shai Halevi, The random oracle methodology, revisited (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.209-218, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276741]
• 9: N. Dedic, G. Itkis, L. Reyzin and S. Russell. Upper and Lower Bounds on Black-Box Steganography. To appear in Theory of Cryptography Conference (TCC), 2005.
• 10: Cynthia Dwork , Larry Stockmeyer , Moni Naor , Omer Reingold, Magic Functions, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.523, October 17-18, 1999
• 11: Zvi Galil , Stuart Haber , Moti Yung, Cryptographic Computation: Secure Faut-Tolerant Protocols and the Public-Key Model, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.135-155, August 16-20, 1987
• 12: O. Goldreich. Secure Multi-Party Computation. Unpublished Manuscript. http://philby.ucsd.edu/books.html, 1998.
• 13: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 14: 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]
• 15: Shafi Goldwasser , Yael Tauman Kalai, On the (In)security of the Fiat-Shamir Paradigm, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.102, October 11-14, 2003
• 16: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 17: 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
• 18: M. Naor. Bit Commitment Using Pseudorandomness. J. Cryptology 4(2): 151--158 (1991)
• 19: Moni Naor , Benny Pinkas, Efficient oblivious transfer protocols, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 07-09, 2001, Washington, D.C., United States
• 20: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 21: B. Pinkas. Fair Secure Two-Party Computation. In: Advances in Cryptology -- Eurocrypt '03, pp 87--105, 2003.
• 22: A. C. Yao. Protocols for Secure Computation. Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982, pages 160--164.
• 23: A. C. Yao. How to Generate and Exchange Secrets. Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, 1986, pages 162--167.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.m MISCELLANEOUS

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Algorithms, Security, Theory

Keywords:
covert computation, fair two-party computation, steganography, two-party computation