Home‎ > ‎

CS 606: Advanced Topics in Cryptography

Summer term (May 16 - July 8, 2016) at IIT Gandhingar
A graduate course targeted for M.Tech and PhD students

Instructor: Souradyuti Paul
  • Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography (draft version) [available freely from authors' homepages]
  • Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography (First edition), CRC Press 
  • Oded Goldreich, Foundations of Cryptography, Basic Tools
  • Oded Goldreich, Foundations of Cryptography, Basic Applications (Vol II)
  • Rafael Pass & Abhi Shelat, A Course in Cryptography, Online publication (available freely).
  • Carmit Hazay and Yehuda Lindlell, Efficient Secure Two-party Protocols (Techniques and Constructions), 2010, Springer.  
Total course credits: 4

Course schedule and contents
Lect #.
 Day  Date  Topics, lecture notes and further reading  Home assignments  Practice Problems
 1  We May 18 Perfect security of a cipher
- Definition and construction: [KL] Def. 2.1, Lemmas 2.2 & 2.3, Def. 2.4, Theo. 2.6 & 2.7 
Prop. 2.5 [KL]
2 Fr May
- Definition and construction (cont.): [BS] Sect. 2.2.1, Ex. 2.1 to 2.4, Def. 2.1, Theo. 2.1 and 2.2, Ex. 2.5 to 2.6, Theo. 2.4 & 2.5

 3  Mo May 23 
Computational cipher and semantic security
- Definitions (fixed and variable-length messages) & reduction: [BS] Attack game 2.1, Def. 2.2 &2.3, Attack game 2.4, Theo. 2.10
- Negligible function, super-poly, poly-bounded: [BS] Sect. 2.4.1
Theo. 2.7 [BS]   
 4  We May 25             - Definitions (fixed and variable-length messages& reduction: [KL] Def. 3.8, 3.9 & 3.10, Claim 3.11
 5 Th  May 26 
- Definition of PRG and security: [BS] Attack game 3.1
(Note: definition of only fixed-length-input PRG is required)
- Construction of SS-secure cipher (for fixed-length message) from PRG: [BS] Def. 3.1, Sect. 3.2, Theo. 3.1; [KL] Def. 3.15, Construction 3.16, Theo. 3.17.
- Multi-message semantic security and attack on Construction 3.16 of KL: [KL] Def. 3.19, Claim 3.20, Theo. 3.21
 6 Tu  May 31 
- Compositions of PRGs to extend lengths of input/output:  [BS] Theo. 3.2 (parallel construction)
- Hybrid games
   (Further reading, not in syllabus)
   Next-bit test for PRG: [BS] Theo. 3.4 and 3.6
Definition of CPA security of a cipher (for fixed and variable-length messages)
: [KL] Def. 3.22; [BS] Def. 5.2
- Definitions: [KL] Def. 3.24, [BS] Def. 4.2
(Note: distinct PRF definitions are required for fixed-length and variable-length messages-inputs)
- Construction of fixed-length CPA-secure cipher from fixed-length-input PRF: [KL] Constr. 3.25
- Proof of CPA-security of Constr. 3.25 of KLclass note; [KL] Theo. 3.26
- Construction of variable-message-length CPA-secure cipher from fixed-length-input PRF: [KL] Coro. 3.27
(Note: Constructions of PRFs with variable-length messages from PRFs with fixed-length messages are discussed in the context of MAC.)
Compositions of PRGs (variable-length): 
[BS] Theo. 3.3 (Blum-Micali sequential construction)
 7  Th June 2  PRP-security
- Definitions of PRP (or Blockcipher), RP and PRP-security: [BS] Def. 4.1, Sect. 4.1.2
- Definitions of SPRP (or strong Blockcipher), SRP and SPRP-security:  [BS] Sect. 4.1.3; [KL] Sect. 3.6.3
(Note: definition of only fixed-length-input PRP/SPRP is required)
Construction of variable-length CPA-secure cipher from PRP/SPRP (e.g. CBC mode): [KL] Sect. 3.6.4 (no proof) 
 8 Sun June 5 Constructions of PRP/SPRP, PRF and PRG from one another
- Construction of PRF from PRG: [KL] Construction 6.21
- Construction of PRG from PRF: [BS] Sect. 4.4.4, Theo. 4.8 (not covered in class but in syllabus)
- Construction of PRP/SPRP from PRF: [KL] Construction  6.23 (Feistel/Luby-Rackoff blockcipher); [BS] Sect. 4.5 (without proof)
Tu  June  7 
PRF/PRP-switching lemma: [BS] Theo. 4.4 and 4.6
- Difference lemma
CCA security and CCA on Constr. 3.25 of KL, CBC mode and variants[KL] Def. 3.31, CCA on CPA secure ciphers; class note
 (Further reading, not in syllabus)
   One-way function and security: [KL] Def. 6.1, Def 6.3
   One-way permutation and security: [KL] Def. 6.2, Def. 6.3
   Hardcore predicate and security: [KL] Def. 6.5
   Construction of hardcore predicate from One-way function: [KL] Theo. 6.6
   Construction of PRG from One-way permutation+Hardcore predicate: 
[KL] Theo. 6.7 & 6.8
 10 Th June 9
Message authentication and security (against existential forgery under chosen messages): 
- Definitions (for fixed-length & variable-length messages): [KL] Def. 4.1 & 4.2; [BS, sect. 6.1] Def. 6.1 and 6.2
- If f is a secure PRF then it is a secure MAC: [BS, Sect. 6.3] Theo. 6.2 
(Note: This theorem is true for variable-input-length and fixed-input-length messages. Is the converse true?)
- Fixed-message-length MACs based on fixed-message-length PRFs
- Message-length = Output-length: [KL] Construction 4.3 & Theo. 4.4
Message-length >> Output-length:
- CBC MAC: [KL] Construction 4.7 (proof not needed) 
- Cascade MAC: [BS] Sect. 6.4.2 
- Extension attacks: Class note; [BS] 6.4.3  
- Variable-message-length MACs:
- Fixed-output-length
- Design paradigm: PRF(k2, UHF(k1,m)); [BS] Sect. 7.0; [BS] Theo. 7.7 (no proof)
- Encrypted CBC: [BS] Sect. 6.5.1
Encrypted Cascade MAC or NMAC: [BS] Sect. 6.5.1
Further reading, not in syllabus
- MACs based on prefix-free encodings, CMAC, PMAC
 11  Sat June 11 
- Carter-Wegman design paradigm: Enc(k2, DUF(k1,m))
- UHF: [BS, Sect. 7.1] Def. 7.1 and 7.2, Horner's rule (p.254)
(Note: UHF is inherently defined for variable-length-messages)
- Construction and security of UHF: [BS, Sect. 7.2.1 (all except subsection "mathematical details")]  
- DUF and construction: [BS] Def. 7.5 & Lemma 7.8
(Note: DUF is inherently defined for variable-length-messages)
 CW MAC from DUF & PRF[BS] Sect. 7.4, Theo. 7.9 
(randomized MAC)
- Output length depends on message-length: 
[KL] Construction 4.5 & Theo. 4.6 (proof not in syllabus) 
 12 Tu  June 14 
Exam 1;
Computational Model: [OG1, Sect. 1.3] (Probabilistic) Turing machine, complexity classes P & BPP; Non-uniform (or message-length dependent) Turing machine; complexity class P/poly; Proof that BPP is contained in P/poly.
(Can we define membership test in a language in terms of cryptographic challenger-adversary framework?)   
 13 Sat  June 18 
Interactive protocol: [PS] Sect. 4.5, Model of computation (ITM), notation and formalism 
Interactive proof with "unbounded" prover: [PS] Defn. 116.1; Protocol 118.3 (Graph non-isomorphism); Proposition 118.4 (Proof of Protocol 118.3); [Class note] Easy graph-isomorphism protocol (class note); 
Interactive proof with "efficient" prover: [Class note] Easy graph-isomorphism protocol; [PS] Defn. 119.5; Protocol 120.6 (Graph isomorphism); Proposition 120.7 (Proof of protocol 120.6)
(Can GNI problem be solved with an efficient prover?) 
Zero-knowledge encryption: [PS] Def. 111.1, Theo. 112.2
14  Tu June 21 (Honest-verifier) zero-knowledge protocol: [PS] Defs. 121.1 and 121.2; Simulation-based security paradigm
(Note it is defined for only NP languages and efficient provers.)
15  Th  June 23  ZK protocol for GI: Protocol 120.6
Proof of ZK Protocol for GI:
[PS] Design of simulator and proof; Theo. 122.3, 123.4
16  Sat  June 25  ZK protocol for all NP languages: [PS] Graph 3-coloring and and construction of simulator, Protocol 127.5 and 128.7 (based on a commitment scheme whose definitions and constructions are not covered in the class. Use hash functions in a "natural" way to construct a commitment scheme).
2-party secure computation for a function F: Semi-honest adversary: [HL] Sect. 2.2
ZK Protocol for Graph 3-coloring and full proof   
17  Tu    June 28      
18  Th  June 30       
19  Sat  July 2       
20  Tu  July 5