Paper Info
Title
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.
Year
DOI
Venue
2005
10.1145/1060590.1060668
STOC
Keywords
Field
DocType
certain value,covert computation,provably secure steganography,covert two-party computation guarantee,covert two-party computation,secret inputs xa,fair two-party computation,two-party computation,secure function evaluation,steganography,malicious adversary,protocol participant,standard secure two-party computation,provable security,random oracle model,zero knowledge proof
Steganography,Secure multi-party computation,Alice and Bob,Computer security,Computer science,Commitment scheme,Random oracle,Covert,Theoretical computer science,Secure two-party computation,Computation
Conference
ISBN
Citations 
PageRank 
1-58113-960-8
7
0.68
References 
Authors
18
3
Name
Order
Citations
PageRank
Luis von Ahn13461346.66
Nicholas Hopper2146995.76
John Langford35392353.60