Secure two-party computation
Encyclopedia
Secure two-party computation (2PC) is sub-problem of secure multi-party computation (MPC) that has received special attention by researchers because of its close relation to many cryptographic tasks. It is concerned with the question: 'Can two party computation be achieved more efficiently and under weaker security assumptions than general MPC?'
Yao
's protocol for two-party computation only provided security against passive adversaries. 2PC protocols that are secure against active adversaries were proposed by Lindell and Pinkas , Ishai, Prabhakaran and Sahai and Nielsen and Orlandi .
Another solution for this problem, that explicitly works with committed input was proposed by Jarecki and Shmatikov .
that collects the input of the two parties over secure channel
s and returns the result if none of the parties chooses to abort. The cryptographic two-party computation protocol is secure, if it behaves no worse than this ideal protocol, but without the additional trust assumption
s. This is usually modeled using a simulator. The task of the simulator is to act as a wrapper around the idealised protocol to make it appear like the cryptographic protocol. The simulation succeeds with respect to an information theoretic
, respectively computationally bounded adversary if the output of the simulator is equal to, respectively computationally indistinguishable from the output of the cryptographic protocol. A two-party computation protocol is secure, if for all adversaries there exists a successful simulator.
Yao
Andrew Yao
Andrew Chi-Chih Yao is a prominent computer scientist and computational theorist. Yao used the minimax theorem to prove what is now known as Yao's Principle.Yao was born in Shanghai, China...
's protocol for two-party computation only provided security against passive adversaries. 2PC protocols that are secure against active adversaries were proposed by Lindell and Pinkas , Ishai, Prabhakaran and Sahai and Nielsen and Orlandi .
Another solution for this problem, that explicitly works with committed input was proposed by Jarecki and Shmatikov .
Security
The security of a two-party computation protocol is usually defined through a comparison with an idealised scenario that is secure by definition. The idealised scenario involves a trusted partyTrusted third party
In cryptography, a trusted third party is an entity which facilitates interactions between two parties who both trust the third party; The Third Party reviews all critical transaction communications between the parties, based on the ease of creating fraudulent digital content. In TTP models, the...
that collects the input of the two parties over secure channel
Secure channel
In cryptography, a secure channel is a way of transferring data that is resistant to interception and tampering.A confidential channel is a way of transferring data that is resistant to interception, but not necessarily resistant to tampering....
s and returns the result if none of the parties chooses to abort. The cryptographic two-party computation protocol is secure, if it behaves no worse than this ideal protocol, but without the additional trust assumption
Assumption
In logic an assumption is a proposition that is taken for granted, as if it were true based upon presupposition without preponderance of the facts...
s. This is usually modeled using a simulator. The task of the simulator is to act as a wrapper around the idealised protocol to make it appear like the cryptographic protocol. The simulation succeeds with respect to an information theoretic
Information theory
Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...
, respectively computationally bounded adversary if the output of the simulator is equal to, respectively computationally indistinguishable from the output of the cryptographic protocol. A two-party computation protocol is secure, if for all adversaries there exists a successful simulator.
See also
- An important primitive in 2PC is oblivious transferOblivious transferIn cryptography, an oblivious transfer protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece has been transferred....
. - Universal composabilityUniversal composabilityThe framework of Universal Composability is a general-purpose model for the analysis of cryptographic protocols. It guarantees very strong security properties. Protocols remain secure even if arbitrarily composed with other instances of the same or other protocols. Security is defined in the...