You'll find it in any textbook on basics of cryptography, for example Foundations of Cryptography by Goldreich. I have added a figure which sums up the relationship between the primitives: arrow represent reductions (i.e. $A\rightarrow B$ means that primitive $B$ can be constructed in a black-box manner from primitive $A$) and dashed arrows represent separations (i.e. $A$--$> B$ means that primitive $B$ cannot be constructed in a black-box manner from primitive $A$). The asterisk denotes folklore results (but feel free to correct me if it is wrong).
(1. I'll add other primitives (FHE, iO...) and assumptions (Factoring, DLP...) in due course.
- Please correct any mistakes in implications/separations or references.)
Note that this is a screenshot from an active page Relations in Cryptography produced by mti
- C: Commitments
- CFP: claw-free permutation
- CRHF: collision-resistant hash function
- DLP: discrete-logarithm problem
- DS: digital signature
- OWF: one-way function
- OWP: one-way permutation
- TDP: trapdoor permutation
- OT: oblivious transfer
- MPC: multi-party computation
- PKE: public-key encryption
- PRG: pseudo-random generator
- PRF: pseudo-random function
- PRP: pseudo-random permutation
- SKE: symmetric-key encryption
- UOWHF: universal one-way hash function
- ZKP: zero-knowledge proofs for NP
[D]: Damgård. Collision Free Hash Functions and Public Key Signature. Eurocrypt’87.
[GGM] Goldreich, Goldwasser and Micali. How to Construct Random Functions. JACM’86.
[BM] Blum and Micali. How to Generate Cryptographically Strong Sequence of Pseudorandom Bits. SIAM JoC’82.
[EGL] Even, Goldreich and Lempel. A Randomized Protocol for Signing Contracts. CACM’85.
[GMR]: Goldwasser, Micali and Rivest. A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM JoC’88.
[GMW1]: Goldreich, Micali and Wigderson. How to Play any Mental Game: A Completeness Theorem for Protocols with Honest Majority. STOC’87
[GMW2]: Goldreich, Micali and Wigderson. Proofs that Yield Nothing but their Validity or All Languages in NP Have Zero Knowledge Proof. FOCS’86
[H+]: Håstad, Impagliazzo, Levin and Luby. A Pseudorandom Generator from Any One-Way Function. SIAM JoC’99.
[IR] Impagliazzo and Rudich. Limits on the Provable Consequences of One-Way Permutations. STOC’89.
[LR] Luby and Rackoff. How to Construct Pseudorandom Permutations from Pseudorandom Functions. SIAM JoC’88.
[N] Naor. Bit Commitment using Pseudorandom Generator. JoC’91.
[NY] Naor and Yung. Universal One Way Hash Functions and their Cryptographic
[Rom] Rompel. One way Functions are Necessary and Sufficient for Secure Signatures. STOC’90.
[Rud] Rudich. PhD Thesis
[S] Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? Eurocrypt’98
[Y] Yao. Theory and Applications of Trapdoor Functions . FOCS’82
This was the original image of the answer.