Secure two-party computation

Last updated

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 , Bob has wealth , and they wish to compute without revealing the values or .

Contents

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

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

Related Research Articles

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party can prove to another party that a given statement is true, while avoiding conveying to the verifier any information beyond the mere fact of the statement's truth. The intuition underlying zero-knowledge proofs is that it is trivial to prove the possession of certain information by simply revealing it; the challenge is to prove this possession without revealing the information, or any aspect of it whatsoever.

In cryptography, an oblivious transfer (OT) 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.

Secure multi-party computation is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their inputs while keeping those inputs private. Unlike traditional cryptographic tasks, where cryptography assures security and integrity of communication or storage and the adversary is outside the system of participants, the cryptography in this model protects participants' privacy from each other.

Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields.

In cryptography, a private information retrieval (PIR) protocol is a protocol that allows a user to retrieve an item from a server in possession of a database without revealing which item is retrieved. PIR is a weaker version of 1-out-of-n oblivious transfer, where it is also required that the user should not get information about other database items.

In cryptography, a password-authenticated key agreement (PAK) method is an interactive method for two or more parties to establish cryptographic keys based on one or more party's knowledge of a password.

The Diffie–Hellman problem (DHP) is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography and serves as the theoretical basis of the Diffie–Hellman key exchange and its derivatives. The motivation for this problem is that many security systems use one-way functions: mathematical operations that are fast to compute, but hard to reverse. For example, they enable encrypting a message, but reversing the encryption is difficult. If solving the DHP were easy, these systems would be easily broken.

In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish between a function chosen randomly from the PRF family and a random oracle. Pseudorandom functions are vital tools in the construction of cryptographic primitives, especially secure encryption schemes.

In cryptography, a secret sharing scheme is verifiable if auxiliary information is included that allows players to verify their shares as consistent. More formally, verifiable secret sharing ensures that even if the dealer is malicious there is a well-defined secret that the players can later reconstruct. The concept of verifiable secret sharing (VSS) was first introduced in 1985 by Benny Chor, Shafi Goldwasser, Silvio Micali and Baruch Awerbuch.

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently. It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.

Non-interactive zero-knowledge proofs are cryptographic primitives, where information between a prover and a verifier can be authenticated by the prover, without revealing any of the specific information beyond the validity of the statement itself. This function of encryption makes direct communication between the prover and verifier unnecessary, effectively removing any intermediaries. The core trustless cryptography "proofing" involves a hash function generation of a random number, constrained within mathematical parameters determined by the prover and verifier.

<span class="mw-page-title-main">Moti Yung</span> Israeli computer scientist

Mordechai M. "Moti" Yung is a cryptographer and computer scientist known for his work on cryptovirology and kleptography.

In cryptography, server-based signatures are digital signatures in which a publicly available server participates in the signature creation process. This is in contrast to conventional digital signatures that are based on public-key cryptography and public-key infrastructure. With that, they assume that signers use their personal trusted computing bases for generating signatures without any communication with servers.

Matthew Keith "Matt" Franklin is an American cryptographer, and a professor of computer science at the University of California, Davis.

<span class="mw-page-title-main">Yehuda Lindell</span> Israeli cryptographer

Yehuda Lindell is a professor in the Department of Computer Science at Bar-Ilan University where he conducts research on cryptography with a focus on the theory of secure computation and its application in practice. Lindell currently leads the cryptography team at Coinbase.

<span class="mw-page-title-main">Amit Sahai</span> American cryptographer (born 1974)

Amit Sahai is an Indian-American computer scientist. He is a professor of computer science at UCLA and the director of the Center for Encrypted Functionalities.

Garbled circuit is a cryptographic protocol that enables two-party secure computation in which two mistrusting parties can jointly evaluate a function over their private inputs without the presence of a trusted third party. In the garbled circuit protocol, the function has to be described as a Boolean circuit.

In cryptography, indistinguishability obfuscation is a type of software obfuscation with the defining property that obfuscating any two programs that compute the same mathematical function results in programs that cannot be distinguished from each other. Informally, such obfuscation hides the implementation of a program while still allowing users to run it. Formally, iO satisfies the property that obfuscations of two circuits of the same size which implement the same function are computationally indistinguishable.

Brent R. Waters is an American computer scientist, specializing in cryptography and computer security. He is currently a professor of Computer Science at the University of Texas at Austin.

An oblivious pseudorandom function (OPRF) is a cryptographic function, similar to a keyed-hash function, but with the distinction that in an OPRF two parties cooperate to securely compute a pseudorandom function (PRF).

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


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.