CSCI 1510

Introduction to Cryptography and Computer Security

Introduction

Welcome to Cryptography and Computer Security (CSCI 1510) at Brown!

Cryptography is about communication and computation in the presence of an adversary. In this course, we will address questions such as:

Can a secret message be sent over an unsecured channel? How can Alice send a message to Bob such that Bob will understand it but no eavesdropper will? Can we guarantee authenticity of data?
How can Bob be sure that the message he received is indeed from Alice? How can he convince someone else of this fact?
Can we guarantee that it is impossible to cheat in an online game? Can Alice and Bob play cards over the Internet?

To answer these questions, we will first decide what security properties are desirable for the situation at hand. We will then formally define the objects that we wish to derive: encryption schemes, signature schemes, and hash functions. Finally, we will give suitable constructions and prove that they satisfy the definitions we have given.

Besides these foundational cryptographic notions, we will also cover more advanced topics including identity-based encryption, post-quantum cryptography, fully homomorphic encryption, zero-knowledge proofs, secure multi-party computation, and program obfuscation. We will see what security guarantees are desirable, how to properly define these security guarantees, and how to design cryptographic algorithms and protocols that satisfy them.

Lectures take place every Tuesday and Thursday from 10:30 - 11:50 AM, in CIT 101 and on Zoom.

Resources

Quick Links

Textbooks

[KL] Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell
[BS] A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup
[R] The Joy of Cryptography by Mike Rosulek
[G] Foundations of Cryptography by Goldreich (Vol. 1 and Vol. 2)
Lecture notes by Pass-Shelat, Bellare-Goldwasser, Bellare-Rogway, and Ostrovsky

Contact

Homeworks

Homework	Release	Due
Homework 0	Sep 8	Sep 15
Homework 1	Sep 15	Sep 22
Homework 2	Sep 22	Sep 29
Homework 3	Sep 29	Oct 6
Homework 4	Oct 6	Oct 13
Homework 5	Oct 13	Oct 20
Homework 6	Oct 27	Nov 3
Homework 7	Nov 3	Nov 10
Homework 8	Nov 10	Nov 17
Homework 9	Nov 17	Dec 1
Homework 10	Dec 1	Dec 8

Lectures

This schedule is tentative and subject to updates throughout the semester.
* indicates optional reading material.

Date	Topics and Readings	Pre-Lec Notes	Post-Lec Notes	Zoom Rec
Sep 7	Topics: Introduction and overview. Readings: Syllabus [KL 1.1] Cryptography and modern cryptography. *[KL 1.3] Historical ciphers and cryptanalysis.	Pre01.pdf	Post01.pdf	Rec01
Sep 12	Topics: Syntax of symmetric-key encryption scheme. Kerckhoff's principle. Definitions of perfect security. One-time pad. Limitations of perfect security. Readings: [KL 1.2, R 1.1] Encryption syntax and Kerckhoff's principle. [KL 1.4.1] Formal definitions. [KL 2.1-2.3] Perfectly secure encryption. *[KL 2.4] Shannon's theorem.	Pre02.pdf	Post02.pdf	Rec02
Sep 14	Topics: Computational security. Concrete vs asymptotic security. Definition of semantically secure encryption. Readings: [KL 3.1] Computational security (concrete vs asymptotic). [KL 3.2, BS 2.2.2] Semantic security.	Pre03.pdf	Post03.pdf	Rec03
Sep 19	Topics: Definition of semantically secure encryption (continued). Definition of pseudorandom generators (PRGs). Semantically secure encryption scheme from PRG. Proof by reduction. Readings: [KL 3.2, BS 2.2.2] Semantic security. [KL 3.3.1, BS 3.1.1] Definition of PRG. [KL 3.3.2-3.3.3, BS 3.2] Encryption scheme from PRG and proof.	Pre04.pdf	Post04.pdf	Rec04
Sep 21	Topics: Fixed-length encryption from PRG (continued). Security against chosen-plaintext attacks. Pseudorandom functions (PRFs). Readings: [KL 3.3.2-3.3.3, BS 3.2] Encryption scheme from PRG and proof. [KL 3.4.2, BS 5.3] Definition of CPA security. [KL 3.5.1, BS 4.4.1] Definition of PRF.	Pre05.pdf	Post05.pdf	Rec05
Sep 26	Topics: Construction of PRF from PRG (GGM tree). CPA-secure encrytpion scheme from PRF. Hybrid argument. Readings: [BS 4.6] Construction of PRF from PRG. [KL 3.5.1, BS 5.4.1] CPA-secure encryption from PRF and proof.	Pre06.pdf	Post06.pdf	Rec06
Sep 28	Topics: Message authentication codes (MACs). Fixed-length MAC. CBC-MAC. Readings: [KL 4.1-4.2, BS 6.1] Definition of MACs. [KL 4.3.1, BS 6.3] Fixed-length MAC. [KL 4.4] CBC-MAC.	Pre07.pdf	Post07.pdf	Rec07
Oct 3	Topics: CBC-MAC (continued). Security against chosen-ciphertext attacks. Definition of authenticated encryption. Readings: [KL 5.1.2, BS 9.2.2] Definition of CCA security. [KL 5.2, BS 9.1] Definition of authenticated encryption.	Pre08.pdf	Post08.pdf	Rec08
Oct 5	Topics: Constructions and proofs of authenticated encryption. Readings: [KL 5.3.1, BS 9.4] Generic constructions of authenticated encryption. *[KL 5.4] Secure communication sessions.	Pre09.pdf	Post09.pdf	Rec09
Oct 10	Topics: Proof of authenticated encryption (continued). Collision resistant hash function (CRHF). Birthday attacks on CRHF. Merkle–Damgård transform. Readings: [KL 6.1.1, BS 8.1] Definition of CRHF. [KL 6.4.1, BS 8.3] Birthday attacks on CRHF. [KL 6.2, BS 8.4] Merkle–Damgård transform.	Pre10.pdf	Post10.pdf	Rec10
Oct 12	Topics: Hash-and-MAC. Applications of CRHF. Practical constructions of block ciphers. Readings: [KL 6.3.1, BS 8.2] Hash-and-MAC. [KL 6.6] Applications of CRHF. *[BS 8.7, 8.9, 8.10, 8.12] Additional applications of CRHF. [KL 7.2.1] Substitution-Permutation Network (SPN).	Pre11.pdf	Post11.pdf	Rec11
Oct 17	Topics: Substitution-permutation networks (continued). Feistel networks. Data encryption standard (DES). Block cipher modes of operation. Readings: [KL 7.2.1-7.2.5] Practical constructions of block ciphers. [KL 3.6.3, R 8.1] Block cipher modes of operation. [R 5.1, 6.2] PRG from block cipher.	Pre12.pdf	Post12.pdf	Rec12
Oct 19	Topics: Block cipher modes of operation (continued). Practical constructions of hash functions. Midterm review. Selected questions from HW 1-4. Readings: [KL 7.3] Practical constructions of hash functions.	Pre13.pdf		Rec13
Oct 24	In-Class Midterm
Oct 26	Topics: One-way functions. Hard-core predicates. Theoretical constructions of symmetric-key primitives. Readings: [KL 8.1.1-8.1.2] Definition and candidates of one-way functions. [KL 8.1.3, 8.3] Hard-core predicates. [KL 8.2, 8.4] Construction of PRG from OWP. [KL 8.5] Construction of PRF from PRG (GGM tree). [KL 8.7] Assumptions for symmetric-key cryptography.	Pre14.pdf	Post14.pdf	Rec14
Oct 31	Topics: Basic group theory. Factoring and RSA assumptions. Discrete-Log and Diffie-Hellman assumptions. Readings: [KL 9.1.1-9.1.4, 9.3.1] Basic group theory. *[KL 9.2.1-9.2.2] Generating random primes. [KL 9.2.3-9.2.4, BS 10.3] Factoring and RSA assumptions. [KL 9.3.2, BS 10.5] Discrete-Log and Diffie-Hellman assumptions. [KL 9.4, BS 10.6] Cryptographic applications.	Pre15.pdf	Post15.pdf	Rec15
Nov 2	Topics: Factoring/RSA and DLOG/CDH/DDH assumptions. Key exchange and Diffie-Hellman protocol. Public-key encryption definitions. El Gamal encryption. RSA-based encryption. Trapdoor permutations. Readings: [KL 11.3, BS 10.4] Key exchange and Diffie-Hellman protocol. [KL 12.2, BS 11.2-11.3] Public-key encryption definitions. [KL 12.4.1, BS 11.5] El Gamal encryption. [KL 12.5.1-12.5.3] RSA-based encryption. [KL 15.1.1, BS 10.3, Pass-Shelat 2.11] Trapdoor permutations.	Pre16.pdf	Post16.pdf	Rec16
Nov 7	Topics: Public-key encryption from trapdoor permutations. Post-quantum PKE from learning with errors (LWE) assumption. Readings: [KL 15.1.2, BS 11.4] Public-key encryption from trapdoor permutations. *[KL 14.1-14.2] Quantum algorithms and their impact on cryptography. [KL 14.3] Learning with errors (LWE) assumption and Regev encryption.	Pre17.pdf	Post17.pdf	Rec17
Nov 9	Topics: Homomorphic property of encryption schemes. Somewhat homomorphic encryption (SWHE) over integers. SWHE from LWE (GSW). Readings: [Halevi's tutorial Sec. 1] Introduction to FHE. [Paper] A conceptually simple construction of FHE over integers. [Halevi's tutorial Sec. 3] GSW protocol.	Pre18.pdf	Post18.pdf	Rec18
Nov 14	Topics: SWHE from LWE (continued). Bootstrapping SWHE to FHE. Digital signatures. Hash-and-sign paradigm. RSA-based signatures. Random oracle model. Readings: [Halevi's tutorial Sec. 3] GSW protocol. [KL 13.1-13.2] Definition of digital signatures. [KL 13.3] Hash-and-sign paradigm. [KL 13.4] RSA-based signatures.	Pre19.pdf	Post19.pdf	Rec19
Nov 16	Topics: Identification schemes. Fiat-Shamir transform. Schnorr's identification/signature schemes. Definition of zero-knowledge proofs (ZKPs). Readings: [KL 13.5] Signatures from DLOG. [Lindell's notes Sec. 5.3, 6.1] Definition of ZKPs. [Lindell's notes Sec. 6.2] Perfect ZKP for Diffie-Hellman tuples.	Pre20.pdf	Post20.pdf	Rec20
Nov 21	Topics: Perfect ZKP for Diffie-Hellman tuples (continued). ZKP for all NP. Non-interactive zero-knowledge proofs (NIZKs). Readings: [Lindell's notes Sec. 6.2] Perfect ZKP for Diffie-Hellman tuples. [Lindell's notes Sec. 7] ZKP for all NP.	Pre21.pdf	Post21.pdf	Rec21
Nov 23	NO LECTURE (Thanksgiving)
Nov 28	Topics: ZKP for all NP (continued). Non-interactive zero-knowledge proofs (NIZKs). Definitions of secure multi-party computation. Readings: [Lindell's note Sec. 1-2, 5] Motivation, definition, and practical use cases of MPC. [Lindell's tutorial Sec. 4.2, 6.2] Formal definitions for semi-honest and malicious MPC.	Pre22.pdf	Post22.pdf	Rec22
Nov 30	Topics: Definitions of MPC (continued). Private set intersection. Oblivious transfer. Readings: [Paper by Ion et al.] DDH-based PSI-sum with cardinality. [Lindell's note Sec. 3] Feasibility results of MPC. [Chou-Orlandi's paper] A simple OT protocol.	Pre23.pdf	Post23.pdf	Rec23
Dec 5	Topics: Oblivious transfer (continued). Semi-honest MPC for any function (GMW protocol). Malicious MPC (GMW compiler). Readings: [Evans-Kolesnikov-Rosulek's book Ch. 3.2] GMW protocol. [Evans-Kolesnikov-Rosulek's book Ch. 6.5.1] GMW compiler.	Pre24.pdf	Post24.pdf	Rec24
Dec 7	Topics: Program obfuscation. Final review. Readings: *[Jain-Lin-Sahai's paper] Indistinguishability obfuscation from well-founded assumptions.	Pre25.pdf	Post25.pdf	Rec25

Calendar

Zoom links are included in the Google Calendar event, as well as in the Hours queue.