<p>One-way functions are implied by all of these things, and known to imply symmetric encryption and digital signatures. These equivalences are indeed found in (theoretically-focused) text books. </p>

<p>The situation for key exchange and asymmetric (i.e., public-key) encryption is a less clear. Asymmetric encryption implies key exchange.</p>

<p>Implications in the other direction (from OWF to KE or KE to AE) are not known--in fact, there is evidence that there are no black box reductions of this type. This line of work started with the seminal paper of Impagliazzo and Rudich, and is nicely summarized (as of circa 2000) here: groups.csail.mit.edu/cis/pubs/malkin/GKMRV.ps</p>

<p>I think that the simplest generic assumption known to imply asymmetric encryption is the existence of trapdoor injective one-way functions. However, not think all known PKE schemes imply the existence of trapdoor injective OWF (lattice-based schemes imply something messier). So again, there is no simple answer.</p>

<p>Much of this latter material is not covered in standard text books; you have to read papers to find it. (I hope my own answer is up to date!)</p>

CC BY-SA 3.0
2017-06-03T18:24:02.970Z
It seems to me that key exchange trivially implies asymmetric encryption: generate a temporary keypair, compute a shared secret, and  then do AEAD with the (hashed) shared secret as key.
Demi
CC BY-SA 3.0
2017-08-03T14:33:13.600Z
The problem is that key exchange may require several rounds of communication, which asymmetric encryption doesn't allow. So the best one can say is that certain specific types of key exchange (including all the ones that arise in practice) imply asymmetric encryption.
Adam Smith
CC BY-SA 3.0
2017-05-30T01:59:52.457Z
2017-05-30T01:59:52.457Z
Adam Smith
<p>What are some necessary and sufficient conditions for the existence of following?</p>

<ul>
<li>Symmetric encryption (defined here as satisfying $\text{IND-CPA}$ and $\text{INT_CTXT}$)</li>
<li>Asymmetric encryption</li>
<li>Digital signatures</li>
<li>Key exchange</li>
</ul>

<p>Ignore quantum computing for the moment.</p>

CC BY-SA 3.0
2017-05-29T04:53:01.763Z
Have you checked a textbook on foundations of cryptography?  A good one should cover all of these.
D.W.
<cr.crypto-security>
Problems equivalent to the existence of secure cryptosystems?
Demi
# Problems equivalent to the existence of secure cryptosystems?

(Asked by: username_0 on 2017-05-29)

What are some necessary and sufficient conditions for the existence of following?

* Symmetric encryption (defined here as satisfying $\text{IND-CPA}$ and $\text{INT\_CTXT}$)
* Asymmetric encryption
* Digital signatures
* Key exchange

Ignore quantum computing for the moment.

**Tags:** cr.crypto-security

> **Comments:**
> **username_1**: Have you checked a textbook on foundations of cryptography?  A good one should cover all of these.  

---

## 1 answers

### Answer by username_2 on 2017-05-30. Score: 3 | Accepted answer

One-way functions are implied by all of these things, and known to imply symmetric encryption and digital signatures. These equivalences are indeed found in (theoretically-focused) text books.

The situation for key exchange and asymmetric (i.e., public-key) encryption is a less clear. Asymmetric encryption implies key exchange.

Implications in the other direction (from OWF to KE or KE to AE) are not known--in fact, there is evidence that there are no black box reductions of this type. This line of work started with the seminal paper of Impagliazzo and Rudich, and is nicely summarized (as of circa 2000) here: groups.csail.mit.edu/cis/pubs/malkin/GKMRV.ps

I think that the simplest generic assumption known to imply asymmetric encryption is the existence of trapdoor injective one-way functions. However, not think all known PKE schemes imply the existence of trapdoor injective OWF (lattice-based schemes imply something messier). So again, there is no simple answer.

Much of this latter material is not covered in standard text books; you have to read papers to find it. (I hope my own answer is up to date!)

> **Comments:**
> **username_0**: It seems to me that key exchange trivially implies asymmetric encryption: generate a temporary keypair, compute a shared secret, and  then do AEAD with the (hashed) shared secret as key.  
> **username_2**: The problem is that key exchange may require several rounds of communication, which asymmetric encryption doesn't allow. So the best one can say is that certain specific types of key exchange (including all the ones that arise in practice) imply asymmetric encryption.  

---

