## Supplementary material

Supplementary material for the topics covered in the lecture can be found for example in the following books from the Semesterapparat:

[Shoup] = Shoup, Victor, **A computational introduction to number theory and algebra**

[Cormen et al.] = Cormen, Thomas H.; Leiserson, Charles, E.; Rivest, Ronald L. and Stein, Clifford, **Introduction to algorithms**

[Goldreich I] = Goldreich, Oded, **Foundations of cryptography I: Basic tools**

[Katz, Lindel] = Katz, Jonathan and Lindel, Yehuda, **Introduction to modern cryptography**

**Prerequisites and brush-up lectures:**

- Elements of algebra
- Groups: [Shoup, Chapter 6]
- Rings: [Shoup, Chapter 7]
- Fields: [Shoup, Chapter 19]
- Vector Spaces and modules: [Shoup, Chapter 13]
- Polynomials: [Shoup, Chapter 17]
- Matrices: [Shoup, Chapter 14]

- Elements of number theory
- Primes, fund. theorem of arithmetic: [Cormen et al., 31.1]
- GCDs: [Cormen et al., 31.2]
- Modular arithmetic: [Cormen et al., 31.3 and 31.4]
- Chinese Remainder Theorem: [Cormen et al., 31.5]

- Algorithms for algebra and number theory
- Square-and-multiply: [Shoup, 3.4]
- Extended Euclid algorithm: [Shoup, Chapter 4]
- Sorting and Searching: [Cormen et al., 6-8 and 12]
- Factoring polynomials over finite fields: [Cormen et al., 20.3-20.5]

- Basic knowledge of complexity theory: [Cormen et al., 3 and 43]
- Working knowledge of probability and combinatorics: [Shoup, Chapter 8]

Many of the brush up lecture topics are also covered (in a more compact form) in [Katz, Lindel, Chapter III.8, Appendix A and Appendix B].

**Main lecture topics:**

- Security models and security proofs: [Katz, Lindel, Chapter I.1 and II.3]
- Information-theoretic and computational security: [Katz, Lindel, Chapter II.3]
- Pseudorandomness: [Goldreich I, Chapter 3]
- Private Key Encryption: [Katz, Lindel, Chapter II.3]
- Authentication: [Katz, Lindel, Chapter II.4]
- Hash functions: [Katz, Lindel, Chapter II.5]
- Public Key Encryption: [Katz, Lindel, Chapter III.11]
- Signature Schemes: [Katz, Lindel, Chapter III.12]
- Zero-Knowledge Proofs: [Goldreich I, Chapter 4]
- Basic Multiparty Computation Protocols: [Katz, Lindel, Chapter III.13.3]

**References by Lecture:**

- Lecture 3: Historic Ciphers [Katz, Lindel, Chapter I.1.3]
- Lecture 4: [Katz, Lindel, Chapter I.2, II.3.5, II.3.7, II.3.3, II.3.6]
- Lecture 5: [Katz, Lindel, Chapter II.3.3, II.3.5, II.3.6], Even-Mansour Construction [https://link.springer.com/article/10.1007/s001459900025]
- Lecture 6: [Katz, Lindel, Chapter II.6.2, II.3.6]
- Lecture 7: [Katz, Lindel, Chapter II.3.6]
- Lecture 8: [Katz, Lindel, Chapter II.4]
- Lecture 9: [Katz, Lindel, Chapter II.5.1, II.5.4]
- Lecture 10: [Katz, Lindel, Chapter II.5.4, II.5.1, II.5.2]
- Lecture 11: [Katz, Lindel, Chapter II.5.3, II.5.4]