Summer term (May 16  July 8, 2016) at IIT Gandhingar A graduate course targeted for M.Tech and PhD students
Textbooks:
 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 Twoparty 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
20 
 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 variablelength messages) & reduction: [BS] Attack game 2.1, Def. 2.2 &2.3, Attack game 2.4, Theo. 2.10
 Negligible function, superpoly, polybounded: [BS] Sect. 2.4.1

Theo. 2.7 [BS] 

4 
We 
May 25 
 Definitions (fixed and variablelength 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 fixedlengthinput PRG is required)
 Construction of SSsecure cipher (for fixedlength message) from PRG: [BS] Def. 3.1, Sect. 3.2, Theo. 3.1; [KL] Def. 3.15, Construction 3.16, Theo. 3.17.
 Multimessage 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)
Nextbit test for PRG: [BS] Theo. 3.4 and 3.6
=============================
Definition of CPA security of a cipher (for fixed and variablelength messages)
: [KL] Def. 3.22; [BS] Def. 5.2
================================================
PRFsecurity
 Definitions: [KL] Def. 3.24, [BS] Def. 4.2
(Note: distinct PRF definitions are required for fixedlength and variablelength messagesinputs)
 Construction of fixedlength CPAsecure cipher from fixedlengthinput PRF: [KL] Constr. 3.25
 Proof of CPAsecurity of Constr. 3.25 of KL: class note; [KL] Theo. 3.26
 Construction of variablemessagelength CPAsecure cipher from fixedlengthinput PRF: [KL] Coro. 3.27
(Note: Constructions of PRFs with variablelength messages from PRFs with fixedlength messages are discussed in the context of MAC.)

Compositions of PRGs (variablelength):
[BS] Theo. 3.3 (BlumMicali sequential construction)


7 
Th 
June 2 
PRPsecurity
 Definitions of PRP (or Blockcipher), RP and PRPsecurity: [BS] Def. 4.1, Sect. 4.1.2
 Definitions of SPRP (or strong Blockcipher), SRP and SPRPsecurity: [BS] Sect. 4.1.3; [KL] Sect. 3.6.3
(Note: definition of only fixedlengthinput PRP/SPRP is required)
Construction of variablelength CPAsecure 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/LubyRackoff blockcipher); [BS] Sect. 4.5 (without proof)



9 
Tu 
June 7 
PRF/PRPswitching 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)
Oneway function and security: [KL] Def. 6.1, Def 6.3
Oneway permutation and security: [KL] Def. 6.2, Def. 6.3
Hardcore predicate and security: [KL] Def. 6.5
Construction of hardcore predicate from Oneway function: [KL] Theo. 6.6
Construction of PRG from Oneway 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 fixedlength & variablelength 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 variableinputlength and fixedinputlength messages. Is the converse true?)
 Fixedmessagelength MACs based on fixedmessagelength PRFs
 Messagelength = Outputlength: [KL] Construction 4.3 & Theo. 4.4
 Messagelength >> Outputlength:
 CBC MAC: [KL] Construction 4.7 (proof not needed)
 Cascade MAC: [BS] Sect. 6.4.2
 Extension attacks: Class note; [BS] 6.4.3
 Variablemessagelength MACs:
 Fixedoutputlength
 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 prefixfree encodings, CMAC, PMAC



11 
Sat 
June 11 
 CarterWegman 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 variablelengthmessages)
 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 variablelengthmessages)
 CW MAC from DUF & PRF: [BS] Sect. 7.4, Theo. 7.9
(randomized MAC)
 Output length depends on messagelength:
[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; Nonuniform (or messagelength 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 challengeradversary 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 nonisomorphism); Proposition 118.4 (Proof of Protocol 118.3); [Class note] Easy graphisomorphism protocol (class note);
Interactive proof with "efficient" prover: [Class note] Easy graphisomorphism 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?)
Zeroknowledge encryption: [PS] Def. 111.1, Theo. 112.2



14 
Tu 
June 21 
(Honestverifier) zeroknowledge protocol: [PS] Defs. 121.1 and 121.2; Simulationbased 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 3coloring 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).
2party secure computation for a function F: Semihonest adversary: [HL] Sect. 2.2 
ZK Protocol for Graph 3coloring and full proof 

17 
Tu 
June 28 



18 
Th 
June 30 



19 
Sat 
July 2 



20 
Tu 
July 5 



