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

Annual Symposium on Foundations of Computer Science

The relationship between public key encryption and oblivious transfer

Yael Gertner, S. Kannan, Tal Malkin, Omer Reingold, Mahesh Viswanathan

Published Nov 7, 2002• 209 citations
Publisher

Abstract

In this paper we study the relationships among some of the most fundamental primitives and protocols in cryptography: public-key encryption (i.e. trapdoor predicates), oblivious transfer (which is equivalent to general secure multi-party computation), key agreement and trapdoor permutations. Our main results show that public-key encryption and oblivious transfer are incomparable under black-box reductions. These separations are tightly matched by our positive results where a restricted (strong) version of one primitive does imply the other primitive. We also show separations between oblivious transfer and key agreement. Finally, we conclude that neither oblivious transfer nor trapdoor predicates imply trapdoor permutations. Our techniques for showing negative results follow the oracle separations of R. Impagliazzo and S. Rudich (1989).

DOI
10.1109/sfcs.2000.892121

Related papers

Black-Box Constructions of Protocols for Secure Computation

Iftach Haitner, Yuval Ishai, Eyal Kushilevitz +2 more

In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor permutation) in a black-box way only. Until now, all known general constructions for this setting were inherently non-black-box since they required the parties to prove zero-knowledge statements that are related to the computation of the underlying primitive. Our main technical result is a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semihonest parties. As a corollary, we obtain the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which make only a black-box use of semihonest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption. In order to construct this reduction we introduce a new notion of security called privacy in the presence of defensible adversaries. This notion states that if an adversary can produce (retroactively, after the protocol terminates) an input and random tape that make its actions appear to be honest, then it is guaranteed that it learned nothing more than its prescribed output. We then show how to construct defensible oblivious transfer from semihonest oblivious transfer, and malicious oblivious transfer from defensible oblivious transfer, all in a black-box way.

SIAM Journal on Computing•Jan 1, 2011•45 citations

Reducing Complexity Assumptions for Oblivious Transfer.

Kai-Yuen Cheong, Takeshi Koshiba

Reducing the minimum assumptions needed to construct various cryptographic primitives is an important andinteresting task in theoretical cryptography. Oblivious Transfer, one of the most basic cryptographic building blocks, is also studied under this scenario. Reducing the minimum assumptions for Oblivious Transfer seems not an easy task, as there are a few impossibility results under black-box reductions. Until recently, it is widely believed that Oblivious Transfer can be constructed with trapdoor permutations but not trapdoor functions in general. In this paper, we enhance previous results and show one Oblivious Transfer protocol based on a collection of trapdoor functions with some extra properties. We also provide reasons for adding the extra properties and argue that the assumptions in the protocol are nearly minimum.

•Jan 1, 2008•0 citations

Black-box constructions for secure computation

Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell +1 more

It is well known that the secure computation of non-trivial functionalities in the setting of no honest majority requires computational assumptions. We study the way such computational assumptions are used. Specifically, we ask whether the secure protocol can use the underlying primitive (e.g., one-way trapdoor permutation) in a black-box way, or must it be nonblack-box (by referring to the code that computes this primitive)? Despite the fact that many general constructions of cryptographic schemes (e.g., CPA-secure encryption) refer to the underlying primitive in a black-box way only, there are some constructions that are inherently nonblack-box. Indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive).In this paper, we study whether such nonblack-box use is essential. We present protocols that use only black-box access to a family of (enhanced) trapdoor permutations or to a homomorphic public-key encryption scheme. The result is a protocol whose communication complexity is independent of the computational complexity of the underlying primitive (e.g., a trapdoor permutation) and whose computational complexity grows only linearly with that of the underlying primitive. This is the first protocol to exhibit these properties.

ACM Symposium on Theory of Computing (STOC)•May 21, 2006•74 citations

Limits of random oracles in secure computation

Mohammad Mahmoody, Hemanta K. Maji, Manoj Prabhakaran

The seminal result of Impagliazzo and Rudich (STOC 1989) gave a black-box separation between one-way functions and public-key encryption: a public-key encryption scheme cannot be constructed using one-way functions in a black-box way. In addition, their result implied black-box separations between one-way functions and protocols for certain Secure Function Evaluation (SFE) functionalities (in particular, Oblivious Transfer). Surprisingly, however, since then there has been no further progress in separating one-way functions and SFE functionalities. In this work, we present the complete picture for finite deterministic 2-party SFE functionalities, vis a vis one-way functions. We show that in case of semi-honest adversaries, one-way functions are black-box separated from all such SFE functionalities, except the ones which have unconditionally secure protocols (and hence do not rely on any computational hardness). In the case of active adversaries, a black-box one-way function is indeed useful for SFE, but we show that it is useful only as much as access to an ideal commitment functionality is useful.

Conference on Innovations in Theoretical Computer Science•Jan 12, 2014•12 citations

Limits of Random Oracles in Secure Computation

Mohammad Mahmoody, Hemanta K. Maji, Manoj Prabhakaran

The seminal result of Impagliazzo and Rudich (STOC 1989) gave a black-box separation between one-way functions and public-key encryption: informally, a public-key encryption scheme cannot be constructed using one-way functions as the sole source of computational hardness. In addition, this implied a black-box separation between one-way functions and protocols for certain Secure Function Evaluation (SFE) functionalities (in particular, Oblivious Transfer). Surprisingly, however, {\em since then there has been no further progress in separating one-way functions and SFE functionalities} (though several other black-box separation results were shown). In this work, we present the complete picture for deterministic 2-party SFE functionalities. We show that one-way functions are black-box separated from {\em all such SFE functionalities}, except the ones which have unconditionally secure protocols (and hence do not rely on any computational hardness), when secure computation against semi-honest adversaries is considered. In the case of security against active adversaries, a black-box one-way function is indeed useful for SFE, but we show that it is useful only as much as access to an ideal commitment functionality is useful. Technically, our main result establishes the limitations of random oracles for secure computation.

arXiv:1205.3554•Electronic colloquium on computational complexity•May 16, 2012•2 citations

On Black-Box Complexity and Adaptive, Universal Composability of Cryptographic Tasks

Dana Dachman-Soled

Two main goals of modern cryptography are to identify the minimal assumptions necessary to construct secure cryptographic primitives as well as to construct secure protocols in strong and realistic adversarial models. In this thesis, we address both of these fundamental questions. In the first part of this thesis, we present results on the black-box complexity of two basic cryptographic primitives: non-malleable encryption and optimally-fair coin tossing. Black-box reductions are reductions in which both the underlying primitive as well as the adversary are accessed only in an input-output (or black-box) manner. Most known cryptographic reductions are black-box. Moreover, black-box reductions are typically more efficient than non-black-box reductions. Thus, the black-box complexity of cryptographic primitives is a meaningful and important area of study which allows us to gain insight into the primitive. We study the black box complexity of non-malleable encryption and optimally-fair coin tossing, showing a positive result for the former and a negative one for the latter. Non-malleable encryption is a strong security notion for public-key encryption, guaranteeing that it is impossible to "maul" a ciphertext of a message m into a ciphertext of a related message. This security guarantee is essential for many applications such as auctions. We show how to transform, in a black-box manner, any public-key encryption scheme satisfying a weak form of security, semantic security, to a scheme satisfying non-malleability. Coin tossing is perhaps the most basic cryptographic primitive, allowing two distrustful parties to flip a coin whose outcome is 0 or 1 with probability 1/2. A fair coin tossing protocol is one in which the outputted bit is unbiased, even in the case where one of the parties may abort early. However, in the setting where parties may abort early, there is always a strategy for one of the parties to impose bias of Omega(1/r) in an r-round protocol. Thus, achieving bias of O(1/r) in r rounds is optimal, and it was recently shown that optimally-fair coin tossing can be achieved via a black-box reduction to oblivious transfer. We show that it cannot be achieved via a black-box reduction to one-way function, unless the number of rounds is at least Omega(n/log n), where n is the input/output length of the one-way function. In the second part of this thesis, we present protocols for multiparty computation (MPC) in the Universal Composability (UC) model that are secure against malicious, adaptive adversaries. In the standard model, security is only guaranteed in a stand-alone setting; however, nothing is guaranteed when multiple protocols are arbitrarily composed. In contrast, the UC model, introduced by (Canetti, 2000), considers the execution of an unbounded number of concurrent protocols, in an arbitrary, and adversarially controlled network environment. Another drawback of the standard model is that the adversary must decide which parties to corrupt before the execution of the protocol commences. A more realistic model allows the adversary to adaptively choose which parties to corrupt based on its evolving view during the protocol. In our work we consider the the adaptive UC model, which combines these two security requirements by allowing both arbitrary composition of protocols and adaptive corruption of parties. In our first result, we introduce an improved, efficient construction of non-committing encryption (NCE) with optimal round complexity, from a weaker primitive we introduce called trapdoor-simulatable public key encryption (PKE). NCE is a basic primitive necessary to construct protocols secure under adaptive corruptions and in particular, is used to construct oblivious transfer (OT) protocols secure against semi-honest, adaptive adversaries. Additionally, we show how to realize trapdoor-simulatable PKE from hardness of factoring Blum integers, thus achieving the first construction of NCE from hardness of factoring. In our second result, we present a compiler for transforming an OT protocol secure against a semi-honest, adaptive adversary into one that is secure against a malicious, adaptive adversary. Our compiler achieves security in the UC model, assuming access to an ideal commitment functionality, and improves over previous work achieving the same security guarantee in two ways: it uses black-box access to the underlying protocol and achieves a constant multiplicative overhead in the round complexity. Combining our two results with the work of (Ishai et al., 2008), we obtain the first black-box construction of UC and adaptively secure MPC from trapdoor-simulatable PKE and the ideal commitment functionality.

•Jan 1, 2011•0 citations
In this paper we study the relationships among some of the most fundamental primitives and protocols in cryptography: public-key encryption (i.e. trapdoor predicates), oblivious transfer (which is equivalent to general secure multi-party computation), key agreement and trapdoor permutations. Our main results show that public-key encryption and oblivious transfer are incomparable under black-box reductions. These separations are tightly matched by our positive results where a restricted (strong) version of one primitive does imply the other primitive. We also show separations between oblivious transfer and key agreement. Finally, we conclude that neither oblivious transfer nor trapdoor predicates imply trapdoor permutations. Our techniques for showing negative results follow the oracle separations of R. Impagliazzo and S. Rudich (1989).
In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor permutation) in a black-box way only. Until now, all known general constructions for this setting were inherently non-black-box since they required the parties to prove zero-knowledge statements that are related to the computation of the underlying primitive. Our main technical result is a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semihonest parties. As a corollary, we obtain the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which make only a black-box use of semihonest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption. In order to construct this reduction we introduce a new notion of security called privacy in the presence of defensible adversaries. This notion states that if an adversary can produce (retroactively, after the protocol terminates) an input and random tape that make its actions appear to be honest, then it is guaranteed that it learned nothing more than its prescribed output. We then show how to construct defensible oblivious transfer from semihonest oblivious transfer, and malicious oblivious transfer from defensible oblivious transfer, all in a black-box way.
Reducing the minimum assumptions needed to construct various cryptographic primitives is an important andinteresting task in theoretical cryptography. Oblivious Transfer, one of the most basic cryptographic building blocks, is also studied under this scenario. Reducing the minimum assumptions for Oblivious Transfer seems not an easy task, as there are a few impossibility results under black-box reductions. Until recently, it is widely believed that Oblivious Transfer can be constructed with trapdoor permutations but not trapdoor functions in general. In this paper, we enhance previous results and show one Oblivious Transfer protocol based on a collection of trapdoor functions with some extra properties. We also provide reasons for adding the extra properties and argue that the assumptions in the protocol are nearly minimum.
It is well known that the secure computation of non-trivial functionalities in the setting of no honest majority requires computational assumptions. We study the way such computational assumptions are used. Specifically, we ask whether the secure protocol can use the underlying primitive (e.g., one-way trapdoor permutation) in a black-box way, or must it be nonblack-box (by referring to the code that computes this primitive)? Despite the fact that many general constructions of cryptographic schemes (e.g., CPA-secure encryption) refer to the underlying primitive in a black-box way only, there are some constructions that are inherently nonblack-box. Indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive).In this paper, we study whether such nonblack-box use is essential. We present protocols that use only black-box access to a family of (enhanced) trapdoor permutations or to a homomorphic public-key encryption scheme. The result is a protocol whose communication complexity is independent of the computational complexity of the underlying primitive (e.g., a trapdoor permutation) and whose computational complexity grows only linearly with that of the underlying primitive. This is the first protocol to exhibit these properties.
The seminal result of Impagliazzo and Rudich (STOC 1989) gave a black-box separation between one-way functions and public-key encryption: a public-key encryption scheme cannot be constructed using one-way functions in a black-box way. In addition, their result implied black-box separations between one-way functions and protocols for certain Secure Function Evaluation (SFE) functionalities (in particular, Oblivious Transfer). Surprisingly, however, since then there has been no further progress in separating one-way functions and SFE functionalities. In this work, we present the complete picture for finite deterministic 2-party SFE functionalities, vis a vis one-way functions. We show that in case of semi-honest adversaries, one-way functions are black-box separated from all such SFE functionalities, except the ones which have unconditionally secure protocols (and hence do not rely on any computational hardness). In the case of active adversaries, a black-box one-way function is indeed useful for SFE, but we show that it is useful only as much as access to an ideal commitment functionality is useful.
The seminal result of Impagliazzo and Rudich (STOC 1989) gave a black-box separation between one-way functions and public-key encryption: informally, a public-key encryption scheme cannot be constructed using one-way functions as the sole source of computational hardness. In addition, this implied a black-box separation between one-way functions and protocols for certain Secure Function Evaluation (SFE) functionalities (in particular, Oblivious Transfer). Surprisingly, however, {\em since then there has been no further progress in separating one-way functions and SFE functionalities} (though several other black-box separation results were shown). In this work, we present the complete picture for deterministic 2-party SFE functionalities. We show that one-way functions are black-box separated from {\em all such SFE functionalities}, except the ones which have unconditionally secure protocols (and hence do not rely on any computational hardness), when secure computation against semi-honest adversaries is considered. In the case of security against active adversaries, a black-box one-way function is indeed useful for SFE, but we show that it is useful only as much as access to an ideal commitment functionality is useful. Technically, our main result establishes the limitations of random oracles for secure computation.
Two main goals of modern cryptography are to identify the minimal assumptions necessary to construct secure cryptographic primitives as well as to construct secure protocols in strong and realistic adversarial models. In this thesis, we address both of these fundamental questions. In the first part of this thesis, we present results on the black-box complexity of two basic cryptographic primitives: non-malleable encryption and optimally-fair coin tossing. Black-box reductions are reductions in which both the underlying primitive as well as the adversary are accessed only in an input-output (or black-box) manner. Most known cryptographic reductions are black-box. Moreover, black-box reductions are typically more efficient than non-black-box reductions. Thus, the black-box complexity of cryptographic primitives is a meaningful and important area of study which allows us to gain insight into the primitive. We study the black box complexity of non-malleable encryption and optimally-fair coin tossing, showing a positive result for the former and a negative one for the latter. Non-malleable encryption is a strong security notion for public-key encryption, guaranteeing that it is impossible to "maul" a ciphertext of a message m into a ciphertext of a related message. This security guarantee is essential for many applications such as auctions. We show how to transform, in a black-box manner, any public-key encryption scheme satisfying a weak form of security, semantic security, to a scheme satisfying non-malleability. Coin tossing is perhaps the most basic cryptographic primitive, allowing two distrustful parties to flip a coin whose outcome is 0 or 1 with probability 1/2. A fair coin tossing protocol is one in which the outputted bit is unbiased, even in the case where one of the parties may abort early. However, in the setting where parties may abort early, there is always a strategy for one of the parties to impose bias of Omega(1/r) in an r-round protocol. Thus, achieving bias of O(1/r) in r rounds is optimal, and it was recently shown that optimally-fair coin tossing can be achieved via a black-box reduction to oblivious transfer. We show that it cannot be achieved via a black-box reduction to one-way function, unless the number of rounds is at least Omega(n/log n), where n is the input/output length of the one-way function. In the second part of this thesis, we present protocols for multiparty computation (MPC) in the Universal Composability (UC) model that are secure against malicious, adaptive adversaries. In the standard model, security is only guaranteed in a stand-alone setting; however, nothing is guaranteed when multiple protocols are arbitrarily composed. In contrast, the UC model, introduced by (Canetti, 2000), considers the execution of an unbounded number of concurrent protocols, in an arbitrary, and adversarially controlled network environment. Another drawback of the standard model is that the adversary must decide which parties to corrupt before the execution of the protocol commences. A more realistic model allows the adversary to adaptively choose which parties to corrupt based on its evolving view during the protocol. In our work we consider the the adaptive UC model, which combines these two security requirements by allowing both arbitrary composition of protocols and adaptive corruption of parties. In our first result, we introduce an improved, efficient construction of non-committing encryption (NCE) with optimal round complexity, from a weaker primitive we introduce called trapdoor-simulatable public key encryption (PKE). NCE is a basic primitive necessary to construct protocols secure under adaptive corruptions and in particular, is used to construct oblivious transfer (OT) protocols secure against semi-honest, adaptive adversaries. Additionally, we show how to realize trapdoor-simulatable PKE from hardness of factoring Blum integers, thus achieving the first construction of NCE from hardness of factoring. In our second result, we present a compiler for transforming an OT protocol secure against a semi-honest, adaptive adversary into one that is secure against a malicious, adaptive adversary. Our compiler achieves security in the UC model, assuming access to an ideal commitment functionality, and improves over previous work achieving the same security guarantee in two ways: it uses black-box access to the underlying protocol and achieves a constant multiplicative overhead in the round complexity. Combining our two results with the work of (Ishai et al., 2008), we obtain the first black-box construction of UC and adaptively secure MPC from trapdoor-simulatable PKE and the ideal commitment functionality.