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 KatzLindell 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:
 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 checkin 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: Noisetolerant learning, the parity
problem, and the statistical query model. J. ACM 50(4): 506519 (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: 191204
 Homomorphic Encryption
 Craig Gentry, Amit Sahai, Brent Waters: Homomorphic Encryption from Learning with Errors: ConceptuallySimpler, AsymptoticallyFaster, AttributeBased. 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): 431473 (1996)
 Elaine Shi, T.H. Hubert Chan, Emil Stefanov, Mingfei Li: Oblivious RAM
with O((logN)3) WorstCase Cost. ASIACRYPT 2011: 197214
 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:
299310
 Honey Decoys in Cryptography
 Ari Juels, Thomas Ristenpart: Honey Encryption: Security Beyond the
BruteForce Bound. EUROCRYPT 2014: 293310
 Ari Juels, Ronald L. Rivest: Honeywords: making passwordcracking detectable. ACM Conference on Computer and Communications Security 2013: 145160
 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 databaseserviceprovider model. SIGMOD
Conference 2002
 Einar Mykletun, Maithili Narasimha, Gene Tsudik: Authentication and
integrity in outsourced databases. TOS 2(2): 107138 (2006)
 Recent Attacks and Proofs for Practical Protocols
 Serge Vaudenay: Security Flaws Induced by CBC Padding  Applications to
SSL, IPSEC, WTLS .... EUROCRYPT 2002: 534546

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:
526540
 Hugo Krawczyk, Kenneth G. Paterson, Hoeteck Wee: On the Security of the
TLS Protocol: A Systematic Analysis. CRYPTO (1) 2013: 429448
 AttributeBased and Functional Encryption
 Sergey Gorbunov, Vinod Vaikuntanathan, Hoeteck Wee: Attributebased
encryption for circuits. STOC 2013.

Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, Dhinakaran Vinayagamurthy: Fully KeyHomomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits. EUROCRYPT 2014:

Shafi Goldwasser, S. Dov Gordon, Vipul Goyal, Abhishek Jain, Jonathan Katz, FengHao Liu, Amit Sahai, Elaine Shi, HongSheng Zhou: Multiinput 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): 895934 (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, MarcelCatalin Rosu, Michael Steiner: HighlyScalable Searchable Symmetric Encryption with Support for Boolean Queries. CRYPTO 2013.
 Attacks against Cryptography in VMs
 Yinqian Zhang, Ari Juels, Michael K. Reiter, Thomas Ristenpart: CrossVM 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): 588613 (2011)
 Will Landecker, Thomas Shrimpton, R. Seth Terashima: Tweakable Blockciphers with Beyond BirthdayBound Security. CRYPTO 2012
 Thomas Shrimpton, R. Seth Terashima: A Modular Framework for Building VariableInputLength Tweakable Ciphers. ASIACRYPT 2013
 Obfuscation
 Amit Sahai, Brent Waters: How to use indistinguishability obfuscation: deniable encryption, and more. STOC 2014