Secure two-party computation: Difference between revisions

Revision as of 00:45, 28 January 2016

Latest revision as of 05:19, 23 May 2025

(21 intermediate revisions by 14 users not shown)

Line 1:

'''Secure two-party computation''' (2PC, or '''secure function evaluation''') is a sub-problem of [[secure multi-party computation]] (MPC) that has received special attention by researchers because of its close relation to many [[cryptographic]] tasks.<ref>{{Citation |last1=Wang |first1=Xiao |title=Faster Secure Two-Party Computation in the Single-Execution Setting |date=2017 |url=http://link.springer.com/10.1007/978-3-319-56617-7_14 |work=Advances in Cryptology – EUROCRYPT 2017 |volume=10212 |pages=399–424 |editor-last=Coron |editor-first=Jean-Sébastien |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-319-56617-7_14 |isbn=978-3-319-56616-0 |access-date=2022-10-19 |last2=Malozemoff |first2=Alex J. |last3=Katz |first3=Jonathan |series=Lecture Notes in Computer Science |editor2-last=Nielsen |editor2-first=Jesper Buus|url-access=subscription }}</ref><ref>{{Cite web |title=MPC Wallet - What is MPC? |url=https://zengo.com/mpc-wallet/ |access-date=2022-10-19 |website=ZenGo |language=en-US}}</ref> 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.<ref>{{Cite book |last1=Henecka |first1=Wilko |last2=K ögl |first2=Stefan |last3=Sadeghi |first3=Ahmad-Reza |last4=Schneider |first4=Thomas |last5=Wehrenberg |first5=Immo |title=Proceedings of the 17th ACM conference on Computer and communications security |chapter=TASTY |date=2010 |chapter-url=http://portal.acm.org/citation.cfm?doid=1866307.1866358 |language=en |___location=Chicago, Illinois, US |publisher=ACM Press |pages=451–462 |doi=10.1145/1866307.1866358 |isbn=978-1-4503-0245-6|s2cid=7276194 |url=https://encrypto.de/papers/HKSSW10.pdf }}</ref> One of the most well known examples of 2PC is [[Yao's Millionaires' Problem|Yao's Millionaires' problem]], in which two parties, Alice and Bob, are millionaires who wish to determine who is wealthier without revealing their wealth.<ref>{{Citation |last1=Lin |first1=Hsiao-Ying |title=An Efficient Solution to the Millionaires' Problem Based on Homomorphic Encryption |date=2005 |work=Applied Cryptography and Network Security |volume=3531 |pages=456–466 |editor-last=Ioannidis |editor-first=John |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |language=en |doi=10.1007/11496137_31 |isbn=978-3-540-26223-7 |last2=Tzeng |first2=Wen-Guey |editor2-last=Keromytis |editor2-first=Angelos |editor3-last=Yung |editor3-first=Moti|doi-access=free }}</ref> Formally, Alice has wealth <math>a</math>, Bob has wealth <math>b</math>, and they wish to compute <math>a \geq b</math> without revealing the values <math>a</math> or <math>b</math>.

'''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?'

[[Andrew Yao|Yao]]'s [[garbled circuit protocol]] for two-party computation only provided security against passive adversaries.<ref>{{Cite journalbook | last1 = Yao | first1 = A. C. | title=23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) |year=1982 |pages=160–164 |chapter=Protocols for secure computations | doi = 10.1109/SFCS.1982.38 |s2cid=206558698}}</ref> One of the first general solutions for achieving security against active adversary was introduced by Goldreich, Micali and Wigderson<ref>{{Cite book|last1=Goldreich|first1=O.|last2=Micali|first2=S.|last3=Wigderson|first3=A.|title=Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 |chapter=How to play ANY mental game |date=1987-01-01|chapter-url=https://doi.org/10.1145/28395.28420|___location=New York, New York, US|publisher=Association for Computing Machinery|pages=218–229|doi=10.1145/28395.28420|isbn=978-0-89791-221-1|s2cid=6669082 }}</ref> by applying Zero-Knowledge Proof to enforce semi-honest behavior.<ref>{{Cite book |last1=Goldwasser 160–164|first1=S |last2=Micali year|first2=S |last3=Rackoff 1982|first3=C |title=Proceedings pmidof the seventeenth annual ACM symposium on Theory of computing - STOC '85 |chapter=The knowledge complexity of interactive proof-systems |date=1985-12-01 pmc|chapter-url=https://doi.org/10.1145/22145.22178 |___location=Providence, Rhode Island, US |publisher=Association for Computing Machinery |pages=291–304 |doi=10.1145/22145.22178 |isbn=978-0-89791-151-1|s2cid=8689051 }}</ref> onlyThis providedapproach securitywas againstknown passiveto adversariesbe 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.<ref>{{Cite book|last1=Abascal|first1=Jackson|last2=Faghihi Sereshgi|first2=Mohammad Hossein|last3=Hazay|first3=Carmit|last4=Ishai|first4=Yuval|last5=Venkitasubramaniam|first5=Muthuramakrishnan|title=Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security |chapter=Is the Classical GMW Paradigm Practical? The Case of Non-Interactive Actively Secure 2PC |date=2020-10-30|chapter-url=https://doi.org/10.1145/3372297.3423366|series=CCS '20|___location=Virtual Event, US|publisher=Association for Computing Machinery|pages=1591–1605|doi=10.1145/3372297.3423366|isbn=978-1-4503-7089-9|s2cid=226228208 }}</ref> Another type of 2PC protocols that are secure against active adversaries were proposed by Yehuda Lindell and Benny Pinkas,<ref>{{Cite journalbook | last1 = Lindell | first1 = Y. | last2title = PinkasAdvances in Cryptology - EUROCRYPT 2007 | first2last2 = B.Pinkas | doifirst2 = 10B.1007/978-3-540-72540-4_4 | titlechapter = An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries | doi = 10.1007/978-3-540-72540-4_4 | volume = 4515 | pages = 52–78 | year = 2007 | pmidseries = Lecture Notes in Computer Science | pmcisbn = 978-3-540-72539-8 }}</ref> Ishai, Manoj Prabhakaran and Sahai[[Amit Sahai]]<ref>{{Cite journalbook | last1 = Ishai | first1 = Y. |title=Advances last2in Cryptology – =CRYPTO 2008 |last2=Prabhakaran | first2 = M. | last3 = Sahai | first3 = A. | title chapter= Founding Cryptography on Oblivious Transfer – Efficiently | doi year=2008 10.1007/|isbn=978-3-540-8517485173-5_328 | volume series=Lecture 5157Notes |in pagesComputer = 572–591Science | year volume= 20085157 | pmid pages= 572–591 | pmc doi= 10.1007/978-3-540-85174-5_32}}</ref> and Jesper Buus Nielsen and Claudio Orlandi.<ref>{{Cite book | last1 = Nielsen | first1 = J. B. | last2 = Orlandi | first2 = C. | doi = 10.1007/978-3-642-00457-5_22 | chapter = LEGO for Two-Party Secure Computation | title = Theory of Cryptography | series = Lecture Notes in Computer Science | volume = 5444 | pages = 368–386 | year = 2009 | isbn = 978-3-642-00456-8 | pmidciteseerx = 10.1.1.215.4422 }}</ref> Another solution for this problem, that explicitly works with committed input was proposed by Stanisław Jarecki and [[Vitaly Shmatikov]].<ref>{{Cite book | pmclast1 = Jarecki | first1 = S. | title = Advances in Cryptology - EUROCRYPT 2007 | last2 = Shmatikov | first2 = V. | chapter = Efficient Two-Party Secure Computation on Committed Inputs | doi = 10.1007/978-3-540-72540-4_6 | volume = 4515 | pages = 97–114 | year = 2007 | series = Lecture Notes in Computer Science | isbn = 978-3-540-72539-8 }}</ref>

Another solution for this problem, that explicitly works with committed input was proposed by Jarecki and Shmatikov.<ref>{{Cite journal | last1 = Jarecki | first1 = S. | last2 = Shmatikov | first2 = V. | doi = 10.1007/978-3-540-72540-4_6 | title = Efficient Two-Party Secure Computation on Committed Inputs | volume = 4515 | pages = 97–114 | year = 2007 | pmid = | pmc = }}</ref>

== Secure multi-party computation ==

{{Main|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.<ref>{{Cite journal |last1=Lindell |first1=Yehuda |last2=Pinkas |first2=Benny |title=An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries |journal=Journal of Cryptology |year=2015 |language=en |volume=28 |issue=2 |pages=312–350 |doi=10.1007/s00145-014-9177-x |s2cid=253638839 |issn=0933-2790|doi-access=free }}</ref> The idealised scenario involves a [[Trusted third party|trusted party]] that collects the input of the two parties mostly client and server over [[secure channel]]s and returns the result if none of the parties chooses to abort.<ref>{{Citation |last1=Crépeau |first1=Claude |title=Statistical Security Conditions for Two-Party Secure Function Evaluation |date=2008 |url=http://link.springer.com/10.1007/978-3-540-85093-9_9 |work=Information Theoretic Security |volume=5155 |pages=86–99 |editor-last=Safavi-Naini |editor-first=Reihaneh |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |language=en |doi=10.1007/978-3-540-85093-9_9 |isbn=978-3-540-85092-2 |access-date=2022-10-19 |last2=Wullschleger |first2=Jürg|series=Lecture Notes in Computer Science |url-access=subscription }}</ref> The cryptographic two-party computation protocol is secure, if it behaves no worse than this ideal protocol, but without the additional [[trust (social sciences)|trust]] [[:wikt:assumption|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 theory|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==

{{reflist}}

<references/>

[[Category:Cryptography]]

{{crypto-stub}}

{{crypto-stub}}

{{Uncategorized|date=January 2016}}