# Overview of relations between cryptographic primitives?

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

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.

1. Please correct any mistakes in implicaitons/separations or references.)

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. OWF: one-way function
10. OWP: one-way permutation
11. OT: oblivious transfer
12. PKE: public-key encryption
13. PRG: pseudo-random generator
14. PRF: pseudo-random function
15. PRP: pseudo-random permutation
16. SKE: symmetric-key encryption
17. UOWHF: universal one-way hash function
18. 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

• @biv should be able to help you with that I think Oct 17 '17 at 21:56
• EGL actually requires an enhanced trapdoor permutation; see Appendix in the second volume of Goldreich's FoC. Oct 18 '17 at 0:27
• @Occams_Trimmer I have been setting up a website for this: Relations in Cryptography. You may want to add it to your answer as a reference. Please also feel free to comment on it. I want to further extend it.
– mti
Oct 23 '17 at 14:59
• The website is not working and in due course is still missing :) Sep 2 '19 at 16:09
• Removed the link to the website. I just don't have enough time at the moment to fix the 'due course' bit. Will try it soon. :) Sep 3 '19 at 8:34