13
$\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

$\endgroup$
8
$\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 implicaitons/separations or references.)

enter image description here

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

$\endgroup$
  • 1
    $\begingroup$ @biv should be able to help you with that I think $\endgroup$ – Ella Rose Oct 17 '17 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 '17 at 0:27
  • 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 '17 at 14:59
  • 1
    $\begingroup$ The website is not working and in due course is still missing :) $\endgroup$ – kelalaka Sep 2 at 16:09
  • 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$ – Occams_Trimmer Sep 3 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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