Covert two-party computation

Luis Von Ahn, Nicholas Hopper, John Langford

Research output: Contribution to journalConference articlepeer-review

20 Scopus citations

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 x A and x B respectively, to compute a function f(x A, x B) 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(x A, x B) 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(x A, x B) 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 zeroknowledge 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.

Original languageEnglish (US)
Pages (from-to)513-522
Number of pages10
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Dec 1 2005
Event13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States
Duration: Nov 7 2005Nov 11 2005

Keywords

  • Covert Computation
  • Fair two-party computation
  • Steganography
  • Two-Party Computation

Fingerprint Dive into the research topics of 'Covert two-party computation'. Together they form a unique fingerprint.

Cite this