Cryptography and Complexity Theory Knowledge Graph

Table of Contents

1. Core Concepts
2. Cryptographic Primitives
3. Complexity Theory Foundations
4. One-Way Functions
5. Hard-Core Predicates
6. Pseudorandom Generators and Variables
7. Computational Indistinguishability
8. One-Way Functions from Pseudorandom Generators
9. Symmetric Key Cryptography
10. Symmetric Key Adversaries
11. Stream Ciphers (IND-CPA)
12. Pseudorandom Functions
13. Pseudorandom Permutations
14. Block Ciphers (IND-CPA)
15. Digital Signatures
16. Hash Functions
17. Lamport Digital Signature Schemes
18. Zero-Knowledge Proofs
19. Authentication and Bit Commitment
20. Public Key Cryptography
21. E-Cash Systems

1. Core Concepts

• cryptographic-protocol.md
• cryptographic-primitive.md
• cryptographic-adversary.md

2. Cryptographic Primitives

Connections to: Symmetric Key and Public Key Cryptography

3. Complexity Theory Foundations

3.1 Basic Models

• turing-machine.md
  • deterministic-turing-machine.md
  • nondeterministic-turing-machine.md
  • probabilistic-turing-machine.md
  • advice-turing-machine.md

3.2 Complexity Classes

Uniform Model:

• p-class-complexity.md
• np-class-complexity.md
• rp-class-complexity.md
• corp-class-complexity.md
• zpp-class-complexity.md
• bpp-class-complexity.md
• pp-class-complexity.md

Non-uniform Model:

• p-poly-class-complexity.md
• scheme-complexity.md

3.3 Algorithmic Concepts

• effective-algorithm.md
• ip-class-complexity.md (shamir-theorem.md)

4. One-Way Functions

• discrete-exponent-problem.md
• discrete-exponent-theorem.md
• weak-one-way-function.md
• yao-one-way-functions-theorem.md
• one-way-function.md (core concept)

5. Hard-Core Predicates

• hard-core-predicate.md
• goldreich-levin-theorem.md

6. Pseudorandom Generators and Variables

• pseudorandom-variable-generator.md
• pseudorandom-variable.md

7. Computational Indistinguishability

• computational-indistinguishability.md
• next-bit-unpredictability.md
• yao-next-bit-criteria.md

8. One-Way Functions from Pseudorandom Generators

• one-way-function-from-pseudorandom-generator.md
• hastad-et-al-theorem.md
• one-way-permutation.md
• yao-pseudorandom-generator-from-permutation.md
• pseudorandom-variable-generator-extension.md

9. Symmetric Key Cryptography

• symmetric-key-cryptosystems.md
• block-cipher.md
• stream-cipher.md

10. Symmetric Key Adversaries

• symmetric-key-adversary.md
• ind-cpa-strong-cryptosystem.md

11. Stream Ciphers (IND-CPA)

• ind-cpa-stream-symmetric-key-cryptosystem-example.md

12. Pseudorandom Functions

• function-generator.md
• pseudorandom-functions.md
• pseudorandom-function-generator.md
• goldreich-et-al-pseudorandom-theorem.md

13. Pseudorandom Permutations

• pseudorandom-permutations.md
• pseudorandom-permutation-generator.md
• feistel-cipher.md
• luby-rackoff-theorem.md

14. Block Ciphers (IND-CPA)

• ind-cpa-block-symmetric-key-cryptosystems.md

15. Digital Signatures

• digital-signature.md
• mac-digital-signature.md
• digital-signature-adversary.md
• eu-cma-model.md

16. Hash Functions

• collision-resistant-hash-functions.md
• universal-one-way-hash-functions.md
• naor-yung-theorem.md
• composition-lemma.md

17. Lamport Digital Signature Schemes

• rompel-theorem.md
• lamport-scheme-one-shot.md
• lamport-scheme-hashing.md
• lamport-scheme-stateful.md
• lamport-scheme-tree.md
• lamport-scheme-stateless.md

18. Zero-Knowledge Proofs

18.1 Basic Concepts

• statistical-distance.md
• statistical-indistinguishability.md
• interactive-proof.md
• interactive-turing-machines.md

18.2 Zero-Knowledge Variants

• statistical-zero-knowledge-proof.md
• computational-zero-knowledge-proof.md
• perfect-zero-knowledge-proof.md

18.3 Examples

• graph-isomorphism-perfect-zero-knowledge-proof.md
• goldreich-et-al-interactive-proof-theorem.md

19. Authentication and Bit Commitment

• authentication-protocol.md
• bit-commitment-scheme.md
• naor-bit-commitment-scheme.md

20. Public Key Cryptography

20.1 Foundations

• public-key-cryptosystem.md
• public-key-adversary.md
• strong-public-key-cryptosystem.md
• trapdoor-function-generator.md

20.2 Number-Theoretic Problems

• quadratic-residue-problem.md
• qr-assumption.md

20.3 Security Models

• ind-koa-strong-cryptosystem.md

20.4 Cryptosystems

• goldwasser-micali-cryptosystem.md
• el-gamal-cryptosystem.md
• rabin-cryptosystem.md

21. E-Cash Systems

• e-cash-system.md
• e-cash-system-example.md
• e-cash-unforgeability.md
• e-cash-anonymity.md
• e-cash-double-spending-prevention.md

Connections and Dependencies

Major Theorems and Results:

1. Yao’s Theorems: Connect one-way functions, pseudorandom generators, and computational indistinguishability
2. Goldreich-Levin Theorem: Connects hard-core predicates to one-way functions
3. Naor-Yung Theorem: Relates to hash functions and digital signatures
4. Luby-Rackoff Theorem: Connects pseudorandom functions to pseudorandom permutations via Feistel networks
5. Rompel Theorem: Foundations for Lamport digital signature schemes
6. Shamir Theorem: IP = PSPACE result in complexity theory
7. Hastad et al. Theorem: Pseudorandom generators from one-way permutations

Cryptographic Hierarchy:

• Foundation: Complexity theory classes and Turing machine models
• Core Primitives: One-way functions, hash functions
• Building Blocks: Pseudorandom generators, functions, permutations
• Applications: Symmetric encryption, digital signatures, zero-knowledge proofs, e-cash
• Security Models: Various adversary models (CPA, CMA, KOA)

Key Relationships:

1. One-way functions → Pseudorandom generators → Pseudorandom functions
2. Hash functions → Digital signatures (via Lamport schemes)
3. Pseudorandom permutations → Block ciphers → IND-CPA security
4. Interactive proofs → Zero-knowledge proofs → Authentication protocols
5. Public key primitives → Digital signatures and encryption schemes