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 []
  • 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]



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.