Secure two-party computation

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. The goal of 2PC is to create a generic protocol that allows two parties to jointly compute an arbitrary function on their inputs without sharing the value of their inputs with the opposing party. One of the most well known examples of 2PC is Yao's millionaire problem, in which two parties, Alice and Bob, are millionaires who wish to determine who is wealthier without revealing their wealth. Formally, Alice has wealth , Bob has wealth , and they wish to compute without revealing the values or .

Yao's garbled circuit protocol for two-party computation [1] only provided security against passive adversaries. 2PC protocols that are secure against active adversaries were proposed by Lindell and Pinkas,[2] Ishai, Prabhakaran and Sahai [3] and Nielsen and Orlandi.[4] Another solution for this problem, that explicitly works with committed input was proposed by Jarecki and Shmatikov.[5]

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 party that collects the input of the two parties over secure channels 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 assumptions. 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 statistically close 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.

gollark: I don't think voting would make the government do what you want *either*.
gollark: Plus travel time and possible queueing.
gollark: Yes. It's not very effective, but it at least shows you really don't like the options!
gollark: Solution: don't vote, but then whenever anyone brings up the subject, just change the subject and distract them.
gollark: > Why is the IQ of everyone using Twitter, Facebook, etc all like 40? It’s amazing just how dumb people on social media areThey have incentives to show you stuff which will make you very outraged, to boost engagement.

See also

References
  1. Yao, A. C. (1982). "Protocols for secure computations". 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). pp. 160–164. doi:10.1109/SFCS.1982.38.
  2. Lindell, Y.; Pinkas, B. (2007). Advances in Cryptology - EUROCRYPT 2007. Lecture Notes in Computer Science. 4515. pp. 52–78. doi:10.1007/978-3-540-72540-4_4. ISBN 978-3-540-72539-8.
  3. Ishai, Y.; Prabhakaran, M.; Sahai, A. (2008). Advances in Cryptology – CRYPTO 2008. Lecture Notes in Computer Science. 5157. pp. 572–591. doi:10.1007/978-3-540-85174-5_32. ISBN 978-3-540-85173-8.
  4. Nielsen, J. B.; Orlandi, C. (2009). "LEGO for Two-Party Secure Computation". Theory of Cryptography. Lecture Notes in Computer Science. 5444. pp. 368–386. CiteSeerX 10.1.1.215.4422. doi:10.1007/978-3-642-00457-5_22. ISBN 978-3-642-00456-8.
  5. Jarecki, S.; Shmatikov, V. (2007). Advances in Cryptology - EUROCRYPT 2007. Lecture Notes in Computer Science. 4515. pp. 97–114. doi:10.1007/978-3-540-72540-4_6. ISBN 978-3-540-72539-8.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.