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:



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

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.

Staff

Peihan Miao

Professor | pmiao

Hello! I work on cryptography, theory, and security. I'm excited about bridging the gap between theory and practice in cryptography. Pronouns: she/her/hers

Leah Namisa Rosenbloom

Grad TA | lrosenb3

I am studying cryptography for grassroots organizing with Anna Lysyanskaya and Seny Kamara. My favorite cryptographic primitive is a zero-knowledge proof of knowledge. Pronouns: they/them

Simon Greenblatt

UTA | scamposg

Hi! I'm a second year Cybersecurity Master's student and I like to climb volcanos. Pronouns: he/him/his