Overview of relations between cryptographic primitives?

Question

Is there a web page that gives a graphical (or, alternatively, a textual) overview of known implications and separations between cryptographic primitives?

More specifically, I am looking for something like the following, but more comprehensive and with references to the respective works. (The following graphic is taken from a set of slides by Danny Harnik and Moni Naor that I found on the Internet.)

Update (Jan 24, 2023)

Created an interactive visualization of the relationships between cryptographic primitives and open-sourced it at https://github.com/matthiasgeihs/crypto-graph. Contributions are welcome!

Answer 1

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.

2. 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

Abbreviations

1. C: Commitments
2. CFP: claw-free permutation
3. CRHF: collision-resistant hash function
4. DLP: discrete-logarithm problem
5. DS: digital signature
6. OWF: one-way function
7. OWP: one-way permutation
8. TDP: trapdoor permutation
9. OT: oblivious transfer
10. MPC: multi-party computation
11. PKE: public-key encryption
12. PRG: pseudo-random generator
13. PRF: pseudo-random function
14. PRP: pseudo-random permutation
15. SKE: symmetric-key encryption
16. UOWHF: universal one-way hash function
17. ZKP: zero-knowledge proofs for NP

References.

[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 Application. STOC’89.

[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.