CS 671 - Seminar in Cryptography

Rutgers University, Department of Computer Science, Fall 2014

Course Overview

This seminar is an introduction to research in cryptography. We'll dig below the surface to learn how cryptographic systems work and learn how to rigorously evaluate their security. The topics will be driven (and largely presented) by the class. We will cover topics anywhere on the spectrum from practice to theory with a focus on identifying research questions for course projects.

This course will not teach you everything about how to make your computer secure. We will be looking at cryptography at a theoretical level with a choice of topics that looks toward its practical usage. Interested students should also consider taking CS 419, which gives an introduction to general computer security.

General Information

Instructor: David Cash (david.cash@rutgers.edu, office Hill 411)
Recommended textbook: Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell.
Class meetings: Wednesday 12:00pm -- 1:20pm and Friday 1:40pm -- 3:00pm in Hill 120
Instructor office hours: In Hill 411 by appointment.

Course Structure, Expectations, and Grading

Prerequisites: There are no formal prerequisites for this seminar. All that is required is a general computer science background and some familiarity with discrete probability (e.g., uniform distribution, independence, conditional probability.) Students must be comfortable working to understand new mathematics and proofs.

Course structure: Research in cryptography requires some familiarity with definitions and techniques that aren't covered in the usual CS curriculum. So we will start with a brief introduction to modern cryptography before starting with research papers. In more detail, the first part of this course (8 lectures) will be lectures on modern cryptography, covering parts of the Katz-Lindell textbook. The next part (14 lectures) will be group discussions about research papers selected by the class. The final part will be presentations and discussions of course projects.

Expected work: There are three expected components to participating in the seminar:
1. Reading and class participation: Everyone will be expected to read assigned papers or textbook chapters before each meeting. (We will cover two related papers each week, roughly.)
2. Leading discussion: Students will present at least one paper to the class (perhaps in pairs, depending on enrollment). The goal is to lead a discussion to deeply understand the paper after everyone has given it a first read.
3. Course project: All students will complete a research project involving reading additional papers, identifying a research question, and developing an attempts at solving it. This will be done with instructor's guidance, and with check-in meetings a few times during the semester (schedule to be determined). The projects will conclude with a significant writeup of the chosen area and project results, as well as a presentation to the seminar.

Reading and Project Topics

Learning Parity with Noise
- Nicholas J. Hopper, Manuel Blum: Secure Human Identification Protocols. ASIACRYPT 2001.
- Henri Gilbert, Matthew J. B. Robshaw, Yannick Seurin: How to Encrypt with the LPN Problem. ICALP (2) 2008.
- Avrim Blum, Adam Kalai, Hal Wasserman: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4): 506-519 (2003)
Learning with Errors (Background)
- Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6) (2009).
- Oded Regev: The Learning with Errors Problem (Invited Survey). IEEE Conference on Computational Complexity 2010: 191-204
Homomorphic Encryption
- Craig Gentry, Amit Sahai, Brent Waters: Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. CRYPTO 2013.
- Zvika Brakerski, Vinod Vaikuntanathan: Efficient Fully Homomorphic Encryption from (Standard) LWE. FOCS 2011.
Oblivious RAM
- Oded Goldreich, Rafail Ostrovsky: Software Protection and Simulation on Oblivious RAMs. J. ACM 43(3): 431-473 (1996)
- Elaine Shi, T.-H. Hubert Chan, Emil Stefanov, Mingfei Li: Oblivious RAM with O((logN)3) Worst-Case Cost. ASIACRYPT 2011: 197-214
- Emil Stefanov, Marten van Dijk, Elaine Shi, Christopher W. Fletcher, Ling Ren, Xiangyao Yu, Srinivas Devadas: Path ORAM: an extremely simple oblivious RAM protocol. ACM Conference on Computer and Communications Security 2013: 299-310
Honey Decoys in Cryptography
- Ari Juels, Thomas Ristenpart: Honey Encryption: Security Beyond the Brute-Force Bound. EUROCRYPT 2014: 293-310
- Ari Juels, Ronald L. Rivest: Honeywords: making password-cracking detectable. ACM Conference on Computer and Communications Security 2013: 145-160
Encrypted Databases
- Raluca A. Popa, Catherine M. S. Redfield, Nickolai Zeldovich, Hari Balakrishnan: CryptDB: protecting confidentiality with encrypted query processing. SOSP 2011.
- Hakan Hacigümüs, Balakrishna R. Iyer, Chen Li, Sharad Mehrotra: Executing SQL over encrypted data in the database-service-provider model. SIGMOD Conference 2002
- Einar Mykletun, Maithili Narasimha, Gene Tsudik: Authentication and integrity in outsourced databases. TOS 2(2): 107-138 (2006)
Recent Attacks and Proofs for Practical Protocols
- Serge Vaudenay: Security Flaws Induced by CBC Padding - Applications to SSL, IPSEC, WTLS .... EUROCRYPT 2002: 534-546
- Juliano Rizzo, Thai Duong: Practical Padding Oracle Attacks. WOOT 2010
- Nadhem J. AlFardan, Kenneth G. Paterson: Lucky Thirteen: Breaking the TLS and DTLS Record Protocols. IEEE Symposium on Security and Privacy 2013: 526-540
- Hugo Krawczyk, Kenneth G. Paterson, Hoeteck Wee: On the Security of the TLS Protocol: A Systematic Analysis. CRYPTO (1) 2013: 429-448
Attribute-Based and Functional Encryption
- Sergey Gorbunov, Vinod Vaikuntanathan, Hoeteck Wee: Attribute-based encryption for circuits. STOC 2013.
- Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, Dhinakaran Vinayagamurthy: Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits. EUROCRYPT 2014:
- Shafi Goldwasser, S. Dov Gordon, Vipul Goyal, Abhishek Jain, Jonathan Katz, Feng-Hao Liu, Amit Sahai, Elaine Shi, Hong-Sheng Zhou: Multi-input Functional Encryption. EUROCRYPT 2014.
Searchable Encryption
- Reza Curtmola, Juan A. Garay, Seny Kamara, Rafail Ostrovsky: Searchable symmetric encryption: Improved definitions and efficient constructions. Journal of Computer Security 19(5): 895-934 (2011)
- Seny Kamara, Charalampos Papamanthou, Tom Roeder: Dynamic searchable symmetric encryption. ACM Conference on Computer and Communications Security 2012
- Seny Kamara, Charalampos Papamanthou: Parallel and Dynamic Searchable Symmetric Encryption. Financial Cryptography 2013.
- David Cash, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, Michael Steiner: Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries. CRYPTO 2013.
Attacks against Cryptography in VMs
- Yinqian Zhang, Ari Juels, Michael K. Reiter, Thomas Ristenpart: Cross-VM side channels and their use to extract private keys. ACM Conference on Computer and Communications Security 2012:
- Thomas Ristenpart, Scott Yilek: When Good Randomness Goes Bad: Virtual Machine Reset Vulnerabilities and Hedging Deployed Cryptography. NDSS 2010
Tweakable Blockciphers
- Moses Liskov, Ronald L. Rivest, David Wagner: Tweakable Block Ciphers. J. Cryptology 24(3): 588-613 (2011)
- Will Landecker, Thomas Shrimpton, R. Seth Terashima: Tweakable Blockciphers with Beyond Birthday-Bound Security. CRYPTO 2012
- Thomas Shrimpton, R. Seth Terashima: A Modular Framework for Building Variable-Input-Length Tweakable Ciphers. ASIACRYPT 2013
Obfuscation
- Amit Sahai, Brent Waters: How to use indistinguishability obfuscation: deniable encryption, and more. STOC 2014