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.

  • 4
    $\begingroup$ Have you checked a textbook on foundations of cryptography? A good one should cover all of these. $\endgroup$ – D.W. May 29 '17 at 4:53

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!)

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Demi Jun 3 '17 at 18:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Adam Smith Aug 3 '17 at 14:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.