19
$\begingroup$

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.) Cryptomania and Minicrypt

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!

$\endgroup$
1

1 Answer 1

17
$\begingroup$

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 implications/separations or references.)

enter image description here

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.

enter image description here

$\endgroup$
20
  • 1
    $\begingroup$ @biv should be able to help you with that I think $\endgroup$
    – Ella Rose
    Oct 17, 2017 at 21:56
  • 1
    $\begingroup$ EGL actually requires an enhanced trapdoor permutation; see Appendix in the second volume of Goldreich's FoC. $\endgroup$
    – fkraiem
    Oct 18, 2017 at 0:27
  • 1
    $\begingroup$ I think it would be worth for the community to create a webpage summarizing these relations. Somewhat like the "complexity zoo" webpage. I am thinking about creating such a page. What do you think? Would that be helpful? $\endgroup$
    – mti
    Oct 18, 2017 at 12:57
  • 1
    $\begingroup$ @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. $\endgroup$
    – mti
    Oct 23, 2017 at 14:59
  • 1
    $\begingroup$ 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. :) $\endgroup$
    – ckamath
    Sep 3, 2019 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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