Basic Cryptography

A. Course Objective: Cryptology is concerned with the conceptualization, definition, and construction of computing systems that address security concerns. The objective of this course is to provide a basic understanding of cryptographic concepts, mathematical tools used for cryptography and how to use these tools in solving cryptographic problems, building new cryptographic primitives, analyzing the security of cryptographic protocols, and understanding key management and key exchange issues at a basic level. The focus is given on the basic mathematical tools as well as some new advanced cryptographic tools and the advances in research using those tools.

B. Course Instructor: Dr. Avijit Dutta and Dr. Nilanjan Datta (Session: 2022-23, IAI TCG CREST)

C. Topics Covered

• Introduction: Classical Ciphers, Shannon Cipher, Perfect Security, Computational Ciphers and Semantic Security.

• Encryption: Stream Ciphers, Pseudo random generators, LFSR based stream ciphers, RC4 and its Cryptanalysis; Block ciphers: Design principle, AES and its design rationale, light-weight block cipher design; Security Notions, Modes of operation: ECB, CBC, OFB, Counter mode.

• Cryptanalysis: Goal and power of an adversary; Differential and Linear Cryptanalysis; Some advanced cryptanalysis (integral, impossible differential) and its applications.

• Hash Function: Collision resistant (CR) hash functions, birthday attacks CR hash, The Merkle- Damgard paradigm, Joux’s multi-collsion attacks; Universal hash functions (UHF), constructing UHFs.

• Message Integrity: Message authentication codes (MACs); Designing MACs from CR hash, Case Study: HMAC, Sponge based MACs; Designing MACs from UHF, The Carter-Wegman MACs, Nonce based MACs.

• Authenticated Encryption (AE): Motivation, Security, Designing AE: Generic Paradigm, Integrated AE; Features of AE, Light-weight AE design.

• Public Key Cryptosystems: Basics of Number theory, Number theoretic Algorithm, Primality testing algorithm, Integer Factorization Problem, Discrete Logarithm Problem, Diffie Hellman Key Exchange Protocol, RSA Encryption and Its variants, Elgamal Encryption Scheme, Digital Signatures, Commitment Scheme, Secret Sharing, Fiat-Shamir Identification Scheme.

D. References

[1] D. Boneh, V. Shoup: A Graduate Course in Applied Cryptography. [Online Link].
[2] J. Katz and Y. Lindell: Introduction to Modern Cryptography, Chapman & Hall/CRC, 2007. [Online Link]
[3] D. R. Stinson, M. B. Paterson: Cryptography Theory and Practice, 4th ed., Chapman & Hall/CRC, 2018. [Online Link]
[4] K. Sakiyama, Y. Li and Y. Sasaki: Security of Block Ciphers: From Algorithm Design to Hardware Implementation, Published by Wiley & Sons, Incorporated, John, 2016. ISBN 10: 1118660013. [Available in Library]
[5] V. Shoup: A Computational Introduction to Number Theory and Algebra, Cambridge University Press. [Online Link]

E. Resources

Symmetric Key Cryptography

• Lecture 1: Introduction to Cryptology. [Boardwork]

• Lecture 2: Classical Ciphers and their Cryptanalysis. [Boardwork] [Slide]

• Lecture 3: Perfect Secrecy [Boardwork]

• Lecture 4: Computation Security, Indistingishability under eavesdroppers, Semantic Security [Boardwork]

• Lecture 5: Pseudo-random generators (PRG), Stream Ciphers, Security for Multiple Encryptions, Chosen Plaintext Attacks (CPA) and CPA Security  [Boardwork]

• Lecture 6: Left-or-Right IND-CPA and Real-or-Random IND-CPA, Pseudo-random Functions (PRF), Constructing IND-CPA Secure encryptions from PRF [Boardwork]

• Lecture 7: PRP, SPRP, Modes of Operations: OCB, CBC, OFB, CTR Modes of Encryptions [Boardwork]

• Lecture 8: Tutorial [Problem Sheet] [Boardwork]

• Lecture 9: CCA, CCA Insecurity of some Popular encryption schemes, Message Authentication Code, EUF-CMA, SUF-CMA, Universal Forgery, Secure MAC Construction: PRF (fixed-length), CBC-MAC and it’s variant (variable-length) [Boardwork]

• Lecture 10: Authenticated Encryption, Motivation, Security Definition, AE Construction using Generic Composition, (In)-Security of EaM, EtM and MtE, Importance of Independence of keys in generic composition [Boardwork]

• Lecture 11: Some Problems on PRF, Message authentication codes [Boardwork]

• Lecture 12: An Introduction to Block Ciphers: Confusion-Diffusion, SPN and Feistel Paradigm of Constructing Block Ciphers [Boardwork]

• Lecture 13: AES Block Cipher: Specification and Design Rationale [Boardwork]

• Lecture 14: Block Cipher Cryptanalysis: Goal, Power of the Adversary, Complexity of an Attack; Differential Cryptanalysis: Motivation, Toy Examples [Boardwork] [Slides]

• Lecture 15: Differential Cryptanalysis on AES – 3 round Distinguishing attack and 4 round Key Recovery attack [Boardwork]

• Lecture 16: Wide trail Strategy, Impossible Differential Cryptanalysis: Distinguishing and Key recovery attacks [Boardwork]

• Lecture 17: Integral Cryptanalysis: All, Constant, Balanced Properties, Distinguishing and Key Recovery Attacks [Boardwork]

• Lecture 18: Linear Cryptanalysis: Distinguishing and Key Recovery Attacks [Boardwork] [Slides] [Notes by Hayes]

• Lecture 19: Hash functions, Security properties of a hash function and their implications, Random Oracle Model, Birthday Paradox, Merkle Damgard Hash Construction [Boardwork]

• Lecture 20: Joux’s Multicollision attack on Iterated Hash functions, Constructing Compression functions, Davies Meyer construction, Sponge Hash Mode, Applications of Hash Functions, Merkle Tree [Boardwork</,ark>] 

• Lecture 21: Keyed Hash functions, Security Properties of Keyed Hash: Universal, Almost-Xor-Universal, Regular, Polynomial Hash function and it’s security [Boardwork]

• Lecture 22: Some variants of Polynomial Hash functions and their insecurity, Designing MACs from Hash function: UHF-PRF composition, Wegman-Carter MAC, Nonce-based MACs [Boardwork] 
  
  

Public Key Cryptography

• Lecture 1: Introduction to Basic Number Theory: I [Boardwork]

• Lecture 2: Introduction to Basic Number Theory: II [Boardwork]

• Lecture 3: Number Theoretic Algorithms: I [Boardwork]

• Lecture 4: Number Theoretic Algorithms: II [Boardwork]

• Lecture 5: Primality Testing Algorithm, Introduction to Public Key Encryption [Boardwork]

• Lecture 6: Indistinguishable (multiple) encryption  in the presence of an eavesdropper [Boardwork]

• Lecture 7: Hybrid Encryption [Boardwork]

• Lecture 8: Chinese Remainder Theorem, Factoring Problem, RSA Problem [Boardwork]

• Lecture 9: RSA Algorithm, Insecurity of textbook RSA [Boardwork]

• Lecture 10: Discrete Logarithm Problem, Diffie-Hellman Problem, CDH, DDH, El-Gamal Encryption [Boardwork]

• Lecture 11: CPA Security of El-Gamal Encryption, CCA Security, CCA Insecurity of Textbook RSA and El-Gamal Encryption [Boardwork]

• Lecture 12: Quadratic Residue, Quadratic Non-Residue, Jacobi Symbol [Boardwork]

• Lecture 13: Quadratic Residuosity Problem, Goldwasser-Micali (GM) Encryption Scheme, CPA Security of GM Encryption assuming hardness of Quadratic Residuosity [Boardwork]

• Lecture 14: Digital Signature [Boardwork]

• Lecture 15: Hash then Sign, RSA-FDH and its Security, Identification Scheme and Its Security Notion [Boardwork]

• Lecture 16: Schnorr’s Identification Scheme and its Security [Boardwork]

• Lecture 17: Fiat-Shamir Transformation, Schnorr Signature Scheme [Boardwork]

• Lecture 18: One Time Signature Scheme, Lamport’s Signature Scheme, Stateful Signature Scheme, Chain-based Signature [Boardwork]

• Lecture 19: Chain-based Signature, Tree-based Signature, Stateless Solution [Boardwork]

• Lecture 20: Key Exchange Protocol and its security, Diffie-Hellman Key Exchange, Decisional Diffie-Hellman, Security of Tree-based signature [Boardwork]

• Lecture 21: Public-Key Infrastructure [Boardwork]
  
  

F. Assignments and Practice Problems

• Problems on Classical Ciphers and Perfect Secrecy [SKC Practice Problems]

• Programming Assignments on Number Theoretic Algorithms [PKC Assignment-I] (Deadline: Sep 22, 2022)

• Assignment on Symmetric Key Encryption [SKC Assignment I] (Deadline: Sep 24, 2022)

• Assignment on Blockcipher Cryptanalysis [SKC Assignment II] (Deadline: Dec 02, 2022)

• Assignment on PKE, Identification Scheme and Digital Signature [PKC Assignment III] (Deadline: Dec 31, 2022)