Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

SIAM Journal on Computing

Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols

Iftach Haitner, Kobbi Nissim B, Eran Omri, Ronen Shaltiel, Jad Silbak

Published Jan 1, 2020• 4 citations
Publisher

Abstract

Let $\pi$ be an efficient two-party protocol that, given security parameter $\kappa$, both parties output single bits $X_\kappa$ and $Y_\kappa$, respectively. We are interested in how $(X_\kappa,Y_\kappa)$ “appears” to an efficient adversary that only views the transcript $T_\kappa$. We make the following contributions: (a) We develop new tools to argue about this loose notion and show (modulo some caveats) that for every such protocol $\pi$, there exists an efficient simulator such that the following holds: on input $T_\kappa$, the simulator outputs a pair $(X'_\kappa,Y'_\kappa)$ such that $(X'_\kappa,Y'_\kappa,T_\kappa)$ is (somewhat) computationally indistinguishable from $(X_\kappa,Y_\kappa,T_\kappa)$. (b) We use these tools to prove the following dichotomy theorem: every such protocol $\pi$ is either uncorrelated---it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce $T_\kappa$, but then choose their outputs independently from some product distribution (that is determined in poly-time from $T_\kappa$), or the protocol implies a key-agreement protocol (for infinitely many $\kappa$'s). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. (c) We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. (d) A subsequent work [I. Haitner, N. Makriyannis, and E. Omri, in Theory of Cryptography Conference, Springer, Cham, Switzerland, 2018, pp. 539--562] uses the above dichotomy to makes progress on a long-standing open question regarding the complexity of fair two-party coin-flipping protocols. We also highlight the following two ideas regarding our technique: (a) The simulator algorithm is obtained by a carefully designed “competition” between efficient algorithms attempting to forecast $(X_\kappa,Y_\kappa)|_{T_\kappa=t}$. The winner is used to simulate the outputs of the protocol. (b) Our key-agreement protocol uses the simulation to reduce to an information theoretic setup and is, in some sense, a non-black-box.

DOI
10.1137/19m1236837

Related papers

Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols

Iftach Haitner, Kobbi Nissim B, Eran Omri +2 more

Let $π$ be an efficient two-party protocol that given security parameter $κ$, both parties output single bits $X_κ$ and $Y_κ$, respectively. We are interested in how $(X_κ,Y_κ)$ "appears" to an efficient adversary that only views the transcript $T_κ$. We make the following contributions: $\bullet$ We develop new tools to argue about this loose notion and show (modulo some caveats) that for every such protocol $π$, there exists an efficient simulator such that the following holds: on input $T_κ$, the simulator outputs a pair $(X'_κ,Y'_κ)$ such that $(X'_κ,Y'_κ,T_κ)$ is (somewhat) computationally indistinguishable from $(X_κ,Y_κ,T_κ)$. $\bullet$ We use these tools to prove the following dichotomy theorem: every such protocol $π$ is: - either uncorrelated -- it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce $T_κ$, but then choose their outputs independently from some product distribution (that is determined in poly-time from $T_κ$), - or, the protocol implies a key-agreement protocol (for infinitely many $κ$'s). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. $\bullet$ We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. $\bullet$ A subsequent work of Haitner et al. uses the above dichotomy to makes progress on a longstanding open question regarding the complexity of fair two-party coin-flipping protocols.

arXiv:2105.00765•May 3, 2021•0 citations

Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols

Iftach Haitner, Kobbi Nissim B, Eran Omri +2 more

Let π be an efficient two-party protocol that given security parameter k, both parties output single bits Xkand Yk, respectively. We are interested in how (Xk, Yk) "appears" to an efficient adversary that only views the transcript Tk. We make the following contributions: · We develop new tools to argue about this loose notion, and show (modulo some caveats) that for every such protocol π, there exists an efficient simulator such that the following holds: on input Tk, the simulator outputs a pair (X'k, Y'k) such that (X'k, Y'k, Tk) is (somewhat) computationally indistinguishable from (Xk, Yk, Tk). · We use these tools to prove the following dichotomy theorem: every such protocol π is: - either uncorrelated - it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce Tk, but then choose their outputs independently from some product distribution (that is determined in poly-time from Tk), - or, the protocol implies a key-agreement protocol (for infinitely many k's). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. ·We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. · A subsequent work of Haitner et al. uses the above dichotomy to makes progress on a long-standing open question regarding the complexity of fair two-party coin-flipping protocols. We highlight the following ideas regarding our technique: · The simulator algorithm is obtained by a carefully designed "competition" between efficient algorithms attempting to forecast ((Xk, Yk)|Tk= t). The winner is used to simulate the outputs of the protocol. · Our key-agreement protocol uses the simulation to reduce to an information theoretic setup, and is in some sense non-black box.

Annual Symposium on Foundations of Computer Science•Oct 1, 2018•7 citations

Computational Complexity Implications of Secure Coin-Flipping

Aris Tentes

Modern Cryptography is based on computational intractability assumptions, e.g., Factoring, Discrete Logarithm, Diffie-Helman etc. However, since an assumption might be proven incorrect, there has been a lot of focus in order to construct cryptographic primitives based on the possibly most minimal assumption. The most popular minimal assumption, which is implied by the existence of almost all cryptographic primitives, is the existence of One Way Functions. Coin-Flipping protocols are known to be implied by One-Way Functions, however, a complete characterization of the inverse direction is not known. There was even speculation that weak notions of Coin Flipping Protocols might be strictly weaker than One Way Functions. In this thesis we show that even very weak notions of Coin Flipping protocols do imply One Way Functions. In particular we show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., .499) implies the existence of One Way Functions. This improves upon a recent result of Haitner and Omri [FOCS ’11], who proved this implication for protocols with bias √ 2−1 2 − o(1) ≈ .207. Unlike the former result result, our result also holds for weak coin-flipping protocols.

•Jan 1, 2014•0 citations

An Almost-Optimally Fair Three-Party Coin-Flipping Protocol

Iftach Haitner, Eliad Tsfadia

In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1986, pp. 364--369] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), in any $m$-round coin-flipping protocol the corrupted parties can bias the honest parties' common output bit by $\Omega(\frac 1{m})$. For more than two decades the best known coin-flipping protocols against dishonest majority had bias $\Theta(\frac {\ell}{\sqrt{m}})$, where $\ell$ is the number of corrupted parties. This was changed by a recent breakthrough result of Moran, Naor, and Segev [in Theory of Cryptography, Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 1--18], who constructed an $m$-round, two-party coin-flipping protocol with optimal bias $\Theta(\frac 1 m)$. In a subsequent work, Beimel, Omri, and Orlov [in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 503--513] extended this result to the multiparty case in which less than $\frac23$ of the parties can be corrupted. Still, for the case of $\frac23$ (or more) corrupted parties, the best known protocol had bias $\Theta(\frac {\ell}{\sqrt{m}})$. In particular, this was the state of affairs for the natural three-party case. We take a step toward eliminating the above gap, presenting an $m$-round, three-party coin-flipping protocol, with bias $\frac{O(\log^3 m)}m$. Our approach (which we also apply to the two-party case) does not follow the “threshold round" paradigm used in the work of Moran, Naor, and Segev and Beimel, Omri, and Orlov but rather is a variation of the majority protocol of Cleve used to obtain the aforementioned $\Theta(\frac {\ell}{\sqrt{m}})$-bias protocol.

SIAM Journal on Computing•Jan 1, 2017•17 citations

On the Computational Complexity of Coin Flipping

Hemanta K. Maji, Manoj Prabhakaran, Amit Sahai

Coin flipping is one of the most fundamental tasks in cryptographic protocol design. Informally, a coin flipping protocol should guarantee both (1) Completeness: an honest execution of the protocol by both parties results in a fair coin toss, and (2) Security: a cheating party cannot increase the probability of its desired outcome by any significant amount. Since its introduction by Blum, coin flipping has occupied a central place in the theory of cryptographic protocols. In this paper, we explore what are the implications of the existence of secure coin flipping protocols for complexity theory. As exposited recently by Impagliazzo, surprisingly little is known about this question. Previous work has shown that if we interpret the Security property of coin flipping protocols very strongly, namely that nothing beyond a negligible bias by cheating parties is allowed, then one-way functions must exist. However, for even a slight weakening of this security property (for example that cheating parties cannot bias the outcome by any additive constant ε > 0), the only complexity-theoretic implication that was known was that PSPACE ⊈ BPP. We put forward a new attack to establish our main result, which shows that, informally speaking, the existence of any (weak) coin flipping protocol that prevents a cheating adversary from biasing the output by more than 1/4 - ε implies that NP ⊈ BPP. Furthermore, for constant-round protocols, we show that the existence of any (weak) coin flipping protocol that allows an honest party to maintain any noticeable chance of prevailing against a cheating party implies the existence of (infinitely often) one-way functions.

Annual Symposium on Foundations of Computer Science•Oct 1, 2010•29 citations

On computational intractability assumptions in cryptography

Chandra Chekuri, Manoj Prabhakaran, Hemanta K. Maji

In cryptographic protocols, honest parties would prefer that their security is assured even in presence of adversarial parties who have unbounded computational power. Information theoretic secure realization of cryptographic primitives provides such guarantees; but for most tasks such strong security guarantees cannot be provided for any reasonable notion of security. The standard technique used in cryptography is to assume the existence of some puzzle, whose hard instances are easy to generate but no efficient algorithm can solve them. Such assumptions, which define intractable problems for efficient algorithms, are called computational intractability assumptions. In this work, we motivate a study of computational intractability assumptions which is goal driven and lends support to the fundamental nature of some of the traditional assumptions beyond being historical accidents. Secure multi-party computation deals with the study of constructing secure protocols for general cryptographic tasks which conform to various notions of security. Inspired by complexity theory, we use the notion of reduction to further our understanding of computational intractability assumptions. Our framework explores the hardness of natural assumptions of the form: “Task F can be securely computed given an ideally secure facility for computing G ”. Formally, we characterize the minimal computational intractability assumption which is sufficient to securely realize a functionality using trusted copies of some other functionality. A functionality F reduces to G , similar to the complexity-theoretic notion of reduction, if F can be securely realized when parties can access trusted copies of G . Thus, if F does not reduce to G information-theoretically, we are interested in characterizing the minimal assumption, which is sufficient, to securely realize the reduction of F to G . In our framework, we explore the relative strengths of these minimal computational assumptions. The fundamental problem, then, is to establish relations, like implication, equivalence and separation, among the assumptions which correspond to various reductions. In this work, we further our understanding of the minimal computational assumptions corresponding to such reductions by showing the following results: 1. We identify a spectrum for the set of assumptions that correspond to reduction between a pair of tasks under different security notions. These reductions are implied by the computational intractability assumption: “semi-honest secure protocol for oblivious transfer exists” (sh-OT assumption). Additionally, the information theoretically impossible reductions considered in this thesis imply the assumption: “one-way functions exist” (OWF assumption). We conjecture that OWF assumption is necessary for these reductions. In fact, the reductions considered in this thesis are either information theoretically true, false, equivalent to OWF assumption or equivalent to sh-OT assumption [MPR10a]. We expand our study to encompass reductions involving randomized functionalities and study the consequences of providing parties with a trusted source of common unbiased coins. For a strong notion of security they turn out to be useless and unless sh-OT assumption holds these randomness sources are not useful [MOPR11, MP11]. 2. We [MPS10] seek to lend additional support to the widely believed premise that “non-trivial cryptography entails the existence of one-way functions”. We show that (constant round) weak coin-tossing protocols, imply OWF assumption. For the general problem, i.e. secure weak coin-tossing protocols with polynomial round complexity, we show a slightly weaker implication NP n BPP. 3. Finally, we indicate the possibility of a wide range of intractability assumptions in our spectrum, intermediate to OWF assumption and sh-OT assumption. We show that a class of natural assumptions corresponding to reductions that are relativistically separated from OWF assumption. Similar techniques have been used to show their separation from the assumption that “public-key encryption exists” (PKE assumption) [MMP11]; but these assumptions are not known to imply sh-OT assumption. We conjecture that, in fact, sh-OT assumption is relativistically separated from these assumptions.

•Jan 1, 2011•3 citations
Let π\piπ be an efficient two-party protocol that, given security parameter κ\kappaκ, both parties output single bits XκX_\kappaXκ​ and YκY_\kappaYκ​, respectively. We are interested in how (Xκ,Yκ)(X_\kappa,Y_\kappa)(Xκ​,Yκ​) “appears” to an efficient adversary that only views the transcript TκT_\kappaTκ​. We make the following contributions: (a) We develop new tools to argue about this loose notion and show (modulo some caveats) that for every such protocol π\piπ, there exists an efficient simulator such that the following holds: on input TκT_\kappaTκ​, the simulator outputs a pair (Xκ′,Yκ′)(X'_\kappa,Y'_\kappa)(Xκ′​,Yκ′​) such that (Xκ′,Yκ′,Tκ)(X'_\kappa,Y'_\kappa,T_\kappa)(Xκ′​,Yκ′​,Tκ​) is (somewhat) computationally indistinguishable from (Xκ,Yκ,Tκ)(X_\kappa,Y_\kappa,T_\kappa)(Xκ​,Yκ​,Tκ​). (b) We use these tools to prove the following dichotomy theorem: every such protocol π\piπ is either uncorrelated---it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce TκT_\kappaTκ​, but then choose their outputs independently from some product distribution (that is determined in poly-time from TκT_\kappaTκ​), or the protocol implies a key-agreement protocol (for infinitely many κ\kappaκ's). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. (c) We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. (d) A subsequent work [I. Haitner, N. Makriyannis, and E. Omri, in Theory of Cryptography Conference, Springer, Cham, Switzerland, 2018, pp. 539--562] uses the above dichotomy to makes progress on a long-standing open question regarding the complexity of fair two-party coin-flipping protocols. We also highlight the following two ideas regarding our technique: (a) The simulator algorithm is obtained by a carefully designed “competition” between efficient algorithms attempting to forecast (Xκ,Yκ)∣Tκ=t(X_\kappa,Y_\kappa)|_{T_\kappa=t}(Xκ​,Yκ​)∣Tκ​=t​. The winner is used to simulate the outputs of the protocol. (b) Our key-agreement protocol uses the simulation to reduce to an information theoretic setup and is, in some sense, a non-black-box.
Let πππ be an efficient two-party protocol that given security parameter κκκ, both parties output single bits XκX_κXκ​ and YκY_κYκ​, respectively. We are interested in how (Xκ,Yκ)(X_κ,Y_κ)(Xκ​,Yκ​) "appears" to an efficient adversary that only views the transcript TκT_κTκ​. We make the following contributions: ∙\bullet∙ We develop new tools to argue about this loose notion and show (modulo some caveats) that for every such protocol πππ, there exists an efficient simulator such that the following holds: on input TκT_κTκ​, the simulator outputs a pair (Xκ′,Yκ′)(X'_κ,Y'_κ)(Xκ′​,Yκ′​) such that (Xκ′,Yκ′,Tκ)(X'_κ,Y'_κ,T_κ)(Xκ′​,Yκ′​,Tκ​) is (somewhat) computationally indistinguishable from (Xκ,Yκ,Tκ)(X_κ,Y_κ,T_κ)(Xκ​,Yκ​,Tκ​). ∙\bullet∙ We use these tools to prove the following dichotomy theorem: every such protocol πππ is: - either uncorrelated -- it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce TκT_κTκ​, but then choose their outputs independently from some product distribution (that is determined in poly-time from TκT_κTκ​), - or, the protocol implies a key-agreement protocol (for infinitely many κκκ's). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. ∙\bullet∙ We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. ∙\bullet∙ A subsequent work of Haitner et al. uses the above dichotomy to makes progress on a longstanding open question regarding the complexity of fair two-party coin-flipping protocols.
Let π be an efficient two-party protocol that given security parameter k, both parties output single bits Xkand Yk, respectively. We are interested in how (Xk, Yk) "appears" to an efficient adversary that only views the transcript Tk. We make the following contributions: · We develop new tools to argue about this loose notion, and show (modulo some caveats) that for every such protocol π, there exists an efficient simulator such that the following holds: on input Tk, the simulator outputs a pair (X'k, Y'k) such that (X'k, Y'k, Tk) is (somewhat) computationally indistinguishable from (Xk, Yk, Tk). · We use these tools to prove the following dichotomy theorem: every such protocol π is: - either uncorrelated - it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce Tk, but then choose their outputs independently from some product distribution (that is determined in poly-time from Tk), - or, the protocol implies a key-agreement protocol (for infinitely many k's). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. ·We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. · A subsequent work of Haitner et al. uses the above dichotomy to makes progress on a long-standing open question regarding the complexity of fair two-party coin-flipping protocols. We highlight the following ideas regarding our technique: · The simulator algorithm is obtained by a carefully designed "competition" between efficient algorithms attempting to forecast ((Xk, Yk)|Tk= t). The winner is used to simulate the outputs of the protocol. · Our key-agreement protocol uses the simulation to reduce to an information theoretic setup, and is in some sense non-black box.
Modern Cryptography is based on computational intractability assumptions, e.g., Factoring, Discrete Logarithm, Diffie-Helman etc. However, since an assumption might be proven incorrect, there has been a lot of focus in order to construct cryptographic primitives based on the possibly most minimal assumption. The most popular minimal assumption, which is implied by the existence of almost all cryptographic primitives, is the existence of One Way Functions. Coin-Flipping protocols are known to be implied by One-Way Functions, however, a complete characterization of the inverse direction is not known. There was even speculation that weak notions of Coin Flipping Protocols might be strictly weaker than One Way Functions. In this thesis we show that even very weak notions of Coin Flipping protocols do imply One Way Functions. In particular we show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., .499) implies the existence of One Way Functions. This improves upon a recent result of Haitner and Omri [FOCS ’11], who proved this implication for protocols with bias √ 2−1 2 − o(1) ≈ .207. Unlike the former result result, our result also holds for weak coin-flipping protocols.
In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1986, pp. 364--369] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), in any mmm-round coin-flipping protocol the corrupted parties can bias the honest parties' common output bit by Ω(1m)\Omega(\frac 1{m})Ω(m1​). For more than two decades the best known coin-flipping protocols against dishonest majority had bias Θ(ℓm)\Theta(\frac {\ell}{\sqrt{m}})Θ(m​ℓ​), where ℓ\ellℓ is the number of corrupted parties. This was changed by a recent breakthrough result of Moran, Naor, and Segev [in Theory of Cryptography, Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 1--18], who constructed an mmm-round, two-party coin-flipping protocol with optimal bias Θ(1m)\Theta(\frac 1 m)Θ(m1​). In a subsequent work, Beimel, Omri, and Orlov [in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 503--513] extended this result to the multiparty case in which less than 23\frac2332​ of the parties can be corrupted. Still, for the case of 23\frac2332​ (or more) corrupted parties, the best known protocol had bias Θ(ℓm)\Theta(\frac {\ell}{\sqrt{m}})Θ(m​ℓ​). In particular, this was the state of affairs for the natural three-party case. We take a step toward eliminating the above gap, presenting an mmm-round, three-party coin-flipping protocol, with bias O(log⁡3m)m\frac{O(\log^3 m)}mmO(log3m)​. Our approach (which we also apply to the two-party case) does not follow the “threshold round" paradigm used in the work of Moran, Naor, and Segev and Beimel, Omri, and Orlov but rather is a variation of the majority protocol of Cleve used to obtain the aforementioned Θ(ℓm)\Theta(\frac {\ell}{\sqrt{m}})Θ(m​ℓ​)-bias protocol.
Coin flipping is one of the most fundamental tasks in cryptographic protocol design. Informally, a coin flipping protocol should guarantee both (1) Completeness: an honest execution of the protocol by both parties results in a fair coin toss, and (2) Security: a cheating party cannot increase the probability of its desired outcome by any significant amount. Since its introduction by Blum, coin flipping has occupied a central place in the theory of cryptographic protocols. In this paper, we explore what are the implications of the existence of secure coin flipping protocols for complexity theory. As exposited recently by Impagliazzo, surprisingly little is known about this question. Previous work has shown that if we interpret the Security property of coin flipping protocols very strongly, namely that nothing beyond a negligible bias by cheating parties is allowed, then one-way functions must exist. However, for even a slight weakening of this security property (for example that cheating parties cannot bias the outcome by any additive constant ε > 0), the only complexity-theoretic implication that was known was that PSPACE ⊈ BPP. We put forward a new attack to establish our main result, which shows that, informally speaking, the existence of any (weak) coin flipping protocol that prevents a cheating adversary from biasing the output by more than 1/4 - ε implies that NP ⊈ BPP. Furthermore, for constant-round protocols, we show that the existence of any (weak) coin flipping protocol that allows an honest party to maintain any noticeable chance of prevailing against a cheating party implies the existence of (infinitely often) one-way functions.
In cryptographic protocols, honest parties would prefer that their security is assured even in presence of adversarial parties who have unbounded computational power. Information theoretic secure realization of cryptographic primitives provides such guarantees; but for most tasks such strong security guarantees cannot be provided for any reasonable notion of security. The standard technique used in cryptography is to assume the existence of some puzzle, whose hard instances are easy to generate but no efficient algorithm can solve them. Such assumptions, which define intractable problems for efficient algorithms, are called computational intractability assumptions. In this work, we motivate a study of computational intractability assumptions which is goal driven and lends support to the fundamental nature of some of the traditional assumptions beyond being historical accidents. Secure multi-party computation deals with the study of constructing secure protocols for general cryptographic tasks which conform to various notions of security. Inspired by complexity theory, we use the notion of reduction to further our understanding of computational intractability assumptions. Our framework explores the hardness of natural assumptions of the form: “Task F can be securely computed given an ideally secure facility for computing G ”. Formally, we characterize the minimal computational intractability assumption which is sufficient to securely realize a functionality using trusted copies of some other functionality. A functionality F reduces to G , similar to the complexity-theoretic notion of reduction, if F can be securely realized when parties can access trusted copies of G . Thus, if F does not reduce to G information-theoretically, we are interested in characterizing the minimal assumption, which is sufficient, to securely realize the reduction of F to G . In our framework, we explore the relative strengths of these minimal computational assumptions. The fundamental problem, then, is to establish relations, like implication, equivalence and separation, among the assumptions which correspond to various reductions. In this work, we further our understanding of the minimal computational assumptions corresponding to such reductions by showing the following results: 1. We identify a spectrum for the set of assumptions that correspond to reduction between a pair of tasks under different security notions. These reductions are implied by the computational intractability assumption: “semi-honest secure protocol for oblivious transfer exists” (sh-OT assumption). Additionally, the information theoretically impossible reductions considered in this thesis imply the assumption: “one-way functions exist” (OWF assumption). We conjecture that OWF assumption is necessary for these reductions. In fact, the reductions considered in this thesis are either information theoretically true, false, equivalent to OWF assumption or equivalent to sh-OT assumption [MPR10a]. We expand our study to encompass reductions involving randomized functionalities and study the consequences of providing parties with a trusted source of common unbiased coins. For a strong notion of security they turn out to be useless and unless sh-OT assumption holds these randomness sources are not useful [MOPR11, MP11]. 2. We [MPS10] seek to lend additional support to the widely believed premise that “non-trivial cryptography entails the existence of one-way functions”. We show that (constant round) weak coin-tossing protocols, imply OWF assumption. For the general problem, i.e. secure weak coin-tossing protocols with polynomial round complexity, we show a slightly weaker implication NP n BPP. 3. Finally, we indicate the possibility of a wide range of intractability assumptions in our spectrum, intermediate to OWF assumption and sh-OT assumption. We show that a class of natural assumptions corresponding to reductions that are relativistically separated from OWF assumption. Similar techniques have been used to show their separation from the assumption that “public-key encryption exists” (PKE assumption) [MMP11]; but these assumptions are not known to imply sh-OT assumption. We conjecture that, in fact, sh-OT assumption is relativistically separated from these assumptions.