Show The Graduate Center Menu

Modern Cryptography

Course Rationale

Cryptographic techniques are an essential ingredient in the security mechanisms that pro-

tect the privacy of e-commerce transactions and the secrecy of cloud storage. This course

introduces the fundamental notions underlying the design and evaluation of cryptographic

primitives that are the core of the security protocols that enable our modern way of life.


Course Description

This introductory, graduate-level course covers the theoretical foundations of modern cryp-

tography. Emphasis will be placed on precise denitions, rigorous proof techniques, and anal-

ysis of the relations among the various cryptographic primitives (such as one-way functions,

pseudo-random generators, pseudo-random permutations, and trapdoor permutations).

List of topics includes: computational security, cryptographic hash functions, private-key

encryption, message authentication codes, public-key encryption, digital signatures, commit-

ment schemes.


No prior knowledge of cryptography is required. However, general ease with algorithms and

elementary probability theory, and maturity with mathematical proofs will be assumed.


Learning Objectives

Discuss how cryptography helps to achieve common security goals (data secrecy, mes-

sage integrity, non-repudiation) and tasks (authentication).

Explain the notions of symmetric encryption, hash functions, and message authentica-

tion, and sketch their formal security denitions.

Describe the specics of some of the prominent techniques for encryption, hashing, and

message authentication (e.g., DES, AES, SHA-1, HMAC).

Explain the notions of public-key encryption and digital signatures, and sketch their

formal security denitions.

Describe and implement the specics of some of the prominent techniques for public-

key cryptosystems and digital signature schemes (e.g., Rabin, RSA, ElGamal, DSA,

Schnorr, OAEP, PSS/PSS-R).

Illustrate the dierence between symmetric and public-key cryptography.

Evaluate cryptographic primitives and their implementations for correctness, eciency,

and security.


Course Textbook

Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell. Chapman & Hall/CRC Press, 2007.

Course Topics


 Classical vs. modern cryptography. Information-theoretic security: Shannon's

 denition of perfect secrecy. Vernam's one-time pad. Limitation of the informa-

tion theoretic approach.

2.Computational Hardness and One-Wayness

-One-way functions. One-way permutations. Trapdoor permutations. Concrete

examples: integer multiplication and modular exponentiation.

-Hardcore predicates. Goldreich-Levin construction.

-Pseudo-random generators. Blum-Micali construction. Ecient instantiation:

-Blum-Blum-Shub construction.

-Pseudo-random functions. Goldreich-Goldwasser-Micali construction.

-Pseudo-random permutations. Luby-Racko construction.

-ε-universal, universal one-way, and collision resistant hash functions. Merkle-

Damgaard construction.

-The hash-the-MAC paradigm.

3. Computationally Secure Symmetric Cryptography

 -Denition of secure symmetric encryption: IND, CPA, CCA.

 -Block-ciphers and mode of operations.

 -Message authentication codes.

 -Hash-then-authenticate paradigm.

4. Managing Shared Keys

 -The key distribution problem

 -Die-Hellman Key Exchange

5.Computationally Secure Asymmetric Cryptography

 -Denition of secure asymmetric encryption: IND, CPA, CCA.

 -Ecient constructions (ElGamal, RSA and Rabin's schemes) and padding schemes


 -Blum-Goldwasser construction. Goldwasser-Micali construction.

6.Digital Signatures

 -Denition of secure digital signatures.

 -Lamport's one-time signature scheme.

 -The hash-then-sign paradigm.

 -Rabin and RSA signature schemes. Padding Schemes (PSS, PSSR).

 -Schnorr signature scheme.

 -Signature schemes for multiple messages: chain-based and tree-based construc-


7. A taste of more advanced topics (identication schemes, commitment schemes, secret




Grade will be based on:

  • Class participation: 10%
  • Assignments: 40%
  • Term project (presentation and report): 50%