CS 671 - Seminar in Cryptography
Rutgers University, Department of Computer Science, Fall 2014
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.
- Instructor: David Cash (email@example.com, 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
Expected work: There are three expected components to participating
in the seminar:
- 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.)
- 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.
- 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
Reading and Project Topics
- Learning Parity with Noise
- Nicholas J. Hopper, Manuel Blum: Secure Human Identification Protocols.
- 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:
- 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
- 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:
- 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
- Amit Sahai, Brent Waters: How to use indistinguishability obfuscation: deniable encryption, and more. STOC 2014