Le kiosk
INPG-UJF / SCCI Master-2 (second year) 

Security models: proofs, protocols and politics
Part Security Proofs
 

This page gives the material related to the lectures on the part "Security Proofs" of the Master SCCI course "Security models: proofs, protocols and politics"
For rules and exams, see the main page of the course.

Note for M2R SECR students: see the related assignments page.

Latex model for the lecture notes by the students.

Planning of the lectures

• Introduction: computationally, provably, unconditionally secure; Attack models; Probabilities
• Entropy and perfect secret/unconditional secure cryptosystem
• Provably secure cryptosystem - One-way functions. Polynomial reductions
• One-way hash function
• Pseudo-random generators
• Probabilistic algorithm - Interactive proofs
• Zero-knowledge protocols

• lecture 1
  Chap 1. Introduction: computationally, provably, unconditionally secure; Attack models; Probabilities
  Perfect secret/unconditional secure cryptosystem (proof of Shannon's lower bound). Vernam cipher; extension to an arbitrary group.
  • slides lecture 1
  • training exercises on entropy
• lectures 2 and 3. Provably secure cryptosystem. Polynomial reduction. P, NP, co-NP classes.
  Links between one-way funtions and complexity.
  Links between one-way trapdoor funtions and complexity.
  Discrete exponential and logarithm.
  one way function and one-way trap-door function. Example: Merkle-Hellman
  
  • slides lecture 2: Part a [ Part a] 
    Training exercises on complexity and provable security (LOG and PLOG, El Gamal) [enonce|[ corrige]
  • slides lecture 3: Part b [ provable security ]
    Training exercises on complexity and provable security (LOG and PLOG, El Gamal) [enonce|[ corrige]
  • slides lecture 3: Part c [ Randomized algorithms, one way function and computational security ]
    Training exercises : Undistinguishabiity and Levin's universal one way function
  • Documentations
    • James Massey. Applied Digital Information Theory I (chap 1, P.5-21) and Applied Digital Information Theory II (chap 9, p. 61-65)
    • Oded Goldreich, Introduction to Complexity Theory : see the notes Part I: Things that should have been taught in previous courses .
  • Sanjeev Arora, Boaz Barak, Computational complexity. A modern approach Chap 9, Cryptography [Draft]
• lecture 4
  One-way hash function
  • Part 1 (1h30). Basic security properties. Building provable compression and extension schemes, examples.
  • slides lecture 4 - part 1 (Hash functions and Provable security)
  • Training exercises on hash functions
    • in english: [ questions ] [ answers ] [ questions+answers ]
    • en francais: [ énoncé ] [ corrigé ] [ énoncé+corrigé ]
• lecture 5
  One-way hash function (Part 3 1h30)
  • Part 2 (1h30). Keyed-hash functions. Strongly univeral hash families; Unconditionally secure message authentication codes (MAC).
    Oracle model and (e,q)-adversary. Application to provable security nested-HMAC.
  • slides lecture 4 - part 2.
  • Training exercises on hash functions
    • in english: [ questions ] [ answers ] [ questions+answers ]
    • en francais: [ énoncé ] [ corrigé ] [ énoncé+corrigé ]
  • Continuous control training: 2011 partial exam
• lecture 6
  Pseudo-Random Generators (part 1)
  • slides lecture 6 / pseudo-random generator
  • Training exercises on random generator
    • in english: [ questions ] [ answers ] [ questions+answers ]
    • en francais: [ questions ] [ réponses ] [ questions+réponses]
• lecture 7
  Provably secure Pseudo-random generators (part 2)
  • slides lecture 7 / pseudo-random generator
  • Non-predictability of Blum-Micali generator
    Complement: Notes from Ben Lynn / Dan Boneh
  • Complement: Proof of BBS [Pascal Junod]
• lectures 8 and 9
  Probabilistic algorithm and Interactive proofs Zero-knowledge protocols
  • slides lecture 8 and 9: interactive proofs and zero knowledge
  • Training exercises on quadratic residue (random generators and zero knowledge)
    • in english: [ questions ] [ answers ] [ questions+answers ]
    • en francais: [ énoncé ] [ corrigé ] [ énoncé+corrigé ]
• lecture 10
  Zero-knowledge protocols (end).
  Conclusion lecture: security proofs of other protocols. This lecture illustrates the application of the techniques of provable security covered by the previous lectures by applying them to other protocols:
  • Sharing a secret
  • idenntification scheme
  • Key distribution
  • Exercises on zero-knowledge in english: [ questions ] [ answers ] [ questions+answers ]
  • Assignment 2: [ english ] [ français ]

Some previous final exams: December 2012

Course material, lecture notes, cooperation and cheating,...

• see the main url of the course
• James Massey. Applied Digital Information Theory I (chap 1, P.5-21) and Applied Digital Information Theory II (chap 9, p. 61-65)
• Oded Goldreich, Introduction to Complexity Theory : see the notes Part I: Things that should have been taught in previous courses .
• Fundations of cryptography - A primer. Oded Goldreich. 2005.
• Cryptography: Theory and Practice (available on google books), Douglas Stinson, 3rd edition.
• Handbook of Applied Cryptography Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. CRC Press, 5th printing, 2001.