Secure two-party computation

Secure two-party computation (2PC) a.k.a. Secure function evaluation 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.^[1][2] 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.^[3] One of the most well known examples of 2PC is Yao's Millionaires' problem, in which two parties, Alice and Bob, are millionaires who wish to determine who is wealthier without revealing their wealth.^[4] Formally, Alice has wealth ${\displaystyle a}$, Bob has wealth ${\displaystyle b}$, and they wish to compute ${\displaystyle a\geq b}$ without revealing the values ${\displaystyle a}$ or ${\displaystyle b}$.

Yao's garbled circuit protocol for two-party computation only provided security against passive adversaries.^[5] One of the first general solutions for achieving security against active adversary was introduced by Goldreich, Micali and Wigderson^[6] by applying Zero-Knowledge Proof to enforce semi-honest behavior.^[7] This approach was known to be impractical for years due to high complexity overheads. However, significant improvements have been made toward applying this method in 2PC and Abascal, Faghihi Sereshgi, Hazay, Yuval Ishai and Venkitasubramaniam gave the first efficient protocol based on this approach.^[8] Another type of 2PC protocols that are secure against active adversaries were proposed by Yehuda Lindell and Benny Pinkas,^[9] Ishai, Manoj Prabhakaran and Amit Sahai^[10] and Jesper Buus Nielsen and Claudio Orlandi.^[11] Another solution for this problem, that explicitly works with committed input was proposed by Stanisław Jarecki and Vitaly Shmatikov.^[12]

Secure multi-party computation

Main article: Secure multi-party computation

Security

The security of a two-party computation protocol is usually defined through a comparison with an idealised scenario that is secure by definition.^[13] The idealised scenario involves a trusted party that collects the input of the two parties mostly client and server over secure channels and returns the result if none of the parties chooses to abort.^[14] 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.

See also

• An important primitive in 2PC is oblivious transfer.
• Universal composability

References

1. Wang, Xiao; Malozemoff, Alex J.; Katz, Jonathan (2017), Coron, Jean-Sébastien; Nielsen, Jesper Buus (eds.), "Faster Secure Two-Party Computation in the Single-Execution Setting", Advances in Cryptology – EUROCRYPT 2017, Lecture Notes in Computer Science, vol. 10212, Cham: Springer International Publishing, pp. 399–424, doi:10.1007/978-3-319-56617-7_14, ISBN 978-3-319-56616-0, retrieved 2022-10-19
2. "MPC Wallet - What is MPC?". ZenGo. Retrieved 2022-10-19.
3. Henecka, Wilko; K ögl, Stefan; Sadeghi, Ahmad-Reza; Schneider, Thomas; Wehrenberg, Immo (2010). "TASTY". Proceedings of the 17th ACM conference on Computer and communications security (PDF). Chicago, Illinois, US: ACM Press. pp. 451–462. doi:10.1145/1866307.1866358. ISBN 978-1-4503-0245-6. S2CID 7276194.
4. Lin, Hsiao-Ying; Tzeng, Wen-Guey (2005), Ioannidis, John; Keromytis, Angelos; Yung, Moti (eds.), "An Efficient Solution to the Millionaires' Problem Based on Homomorphic Encryption", Applied Cryptography and Network Security, vol. 3531, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 456–466, doi:10.1007/11496137_31, ISBN 978-3-540-26223-7
5. 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. S2CID 206558698.
6. Goldreich, O.; Micali, S.; Wigderson, A. (1987-01-01). "How to play ANY mental game". Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87. New York, New York, US: Association for Computing Machinery. pp. 218–229. doi:10.1145/28395.28420. ISBN 978-0-89791-221-1. S2CID 6669082.
7. Goldwasser, S; Micali, S; Rackoff, C (1985-12-01). "The knowledge complexity of interactive proof-systems". Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85. Providence, Rhode Island, US: Association for Computing Machinery. pp. 291–304. doi:10.1145/22145.22178. ISBN 978-0-89791-151-1. S2CID 8689051.
8. Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (2020-10-30). "Is the Classical GMW Paradigm Practical? The Case of Non-Interactive Actively Secure 2PC". Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. CCS '20. Virtual Event, US: Association for Computing Machinery. pp. 1591–1605. doi:10.1145/3372297.3423366. ISBN 978-1-4503-7089-9. S2CID 226228208.
9. Lindell, Y.; Pinkas, B. (2007). "An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries". Advances in Cryptology - EUROCRYPT 2007. Lecture Notes in Computer Science. Vol. 4515. pp. 52–78. doi:10.1007/978-3-540-72540-4_4. ISBN 978-3-540-72539-8.
10. Ishai, Y.; Prabhakaran, M.; Sahai, A. (2008). "Founding Cryptography on Oblivious Transfer – Efficiently". Advances in Cryptology – CRYPTO 2008. Lecture Notes in Computer Science. Vol. 5157. pp. 572–591. doi:10.1007/978-3-540-85174-5_32. ISBN 978-3-540-85173-8.
11. Nielsen, J. B.; Orlandi, C. (2009). "LEGO for Two-Party Secure Computation". Theory of Cryptography. Lecture Notes in Computer Science. Vol. 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.
12. Jarecki, S.; Shmatikov, V. (2007). "Efficient Two-Party Secure Computation on Committed Inputs". Advances in Cryptology - EUROCRYPT 2007. Lecture Notes in Computer Science. Vol. 4515. pp. 97–114. doi:10.1007/978-3-540-72540-4_6. ISBN 978-3-540-72539-8.
13. Lindell, Yehuda; Pinkas, Benny (2015). "An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries". Journal of Cryptology. 28 (2): 312–350. doi:10.1007/s00145-014-9177-x. ISSN 0933-2790. S2CID 253638839.
14. Crépeau, Claude; Wullschleger, Jürg (2008), Safavi-Naini, Reihaneh (ed.), "Statistical Security Conditions for Two-Party Secure Function Evaluation", Information Theoretic Security, Lecture Notes in Computer Science, vol. 5155, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 86–99, doi:10.1007/978-3-540-85093-9_9, ISBN 978-3-540-85092-2, retrieved 2022-10-19