# 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.

# 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