Cryptography WS 2014/2015

News | Dates | Grading | Content | Exercises | Material

Expected previous knowledge

You should have a rough idea of the definition of the following terms:

• group, field, modular arithmetic
• discrete probability space, uniform distribution, random variable, stochastic independence, event, conditional probability,
• Turing machine, nondeterminism, polynomial time, P, NP

Preliminary outline

• Theoretical foundations of cryptography
  • Perfect secrecy
  • Computational security (w.r.t. probabilistic polynomial-time adversaries)
    • Attacks: eavesdropping, chosen-plain-text (CPA), chosen-cipher-text (CCA1/2)
  • Cryptographic primitives:
    • Pseudorandomness: Generators (PRG), functions (PRF), (strong) permutations (PRP) as abstractions of secure blockciphers
    • One-way functions (OWF) and permutations (OWP) (with trapdoor information (TDP))
    • Cryptographic hash functions: collision resistance, Merkle-Damgård construction, birthday paradox
  • Relations between cryptographic primitives
  • Relation to complexity theory (P vs NP)
• Private-key encryption and message-authentication codes (MACs)
  • Blockciphers (''practical PRFs/PRPs'')
    • DES, AES
    • Construction principles underlying blockciphers: Feistel networks, substitution-permutation networks
  • Construction of secure encryption schemes from PRFs/PRPs
    • Modes of operation: randomized-counter (rCTR) mode, output-feed-back (OFB) mode, cipher-block-chaining (CBC) mode
    • Tweakable blockciphers: XEX-mode
  • Construction of secure MACs from PRFs
    • Domain-extension of PRFs, NMAC, HMAC
• Public-key encryption and signatures
  • Algebraic and number theoretical foundations
    • Factoring and the RSA problem, trapdoor one-way permutations
    • Discrete logarithm and the computational and decisional Diffie-Hellman (CDH/DDH) problems, elliptic curves
  • Diffie-Hellman key exchange
  • Public-key encryption schemes:
    • Based on the RSA problem: RSA PKCS #1 v1.5, RSA-OAEP
    • Based on the DDH problem: El Gamal, hashed Diffie-Hellman
    • Hybrid encryption: Diffie-Hellman key exchange as key-encapsulating mechanism (KEM)
    • (Lattice based)
  • Digital signature schemes:
    • Related to the RSA problem: RSA-FDH, RSA-PSS
    • Related to the discrete logarithm: El Gamal's signature scheme, DSA