CSE 208: Papers

Below are some suggestions for papers and topics that we can cover. The list is neither rigid nor exhaustive. You are welcome to propose other papers and topics.

It seems embarrassing, in the current climate, to call oneself a cryptographer and not know something about the cryptanalysis of the hash functions that we are seeing being attacked. So I think we should study the following paper and acquaint ourselves with the cryptanalysis of MD5.

[BlCoHi] John Black, Martin Cochran, and Trevor Highland. A Study of the MD5 Attacks: Insights and Improvements.

Hash functions being the most important and immediate problem facing our community, I'd be happy to pursue it further. You're welcome to propose further papers on this topic.

The following paper elegantly resolves some long-standing open questions regarding cryptographic primitives, and also provides a tool that is proving useful for many things.

[PeWa] Chris Peikert and Brent Waters. Lossy Trapdoor Functions and their Applications.

The unifying theme of the following papers is to implement IBE without pairings. Both papers introduce potentially useful new primitives.

[BoGeHa] Dan Boneh, Craig Gentry, and Michael Hamburg. Space-Efficient Identity Based Encryption Without Pairings.
[GePeVa] Craig Gentry, Chris Peikert, Vinod Vaikuntanathan. Trapdoors for Hard Lattices and New Cryptographic Constructions.

Next is the sequence of papers on the Cramer-Shoup encryption scheme and its successor, the Kurosawa-Desmedt encryption scheme. These are important schemes whose techniques have been influential.

[CrSh1] Ronald Cramer and Victor Shoup. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack.
[GeSh] Rosario Gennaro and Victor Shoup. A note on an encryption scheme of Kurosawa and Desmedt. This result was published as part of the extended abstract Tag-KEM/DEM: A new framework for hybrid encryption and a new analysis of Kurosawa-Desmedt KEM, by Abe, Gennaro, Kurosawa, and Shoup.
[HoKi] Dennis Hofheinz and Eike Kiltz. Secure Hybrid Encryption from Weakened Key Encapsulation.

The following paper presents a new approach for Diffie Hellman based cryptography that simplifies and strengthens previous ones.

[CaKiSh] David Cash, Eike Kiltz and Victor Shoup. The Twin Diffie-Hellman Problem and Applications.

The Cramer-Shoup signature scheme is the best known one without random oracles, and again represents some interesting techniques. Bernstein's paper is a nice advance for signatures with tight security.

[CaSh2] Ronald Cramer and Victor Shoup. Signature schemes based on the Strong RSA Assumption.
[Fi] Marc Fischlin. The Cramer-Shoup Strong-RSA Signature Scheme Revisited.
[Be] Daniel J. Bernstein. Proving Tight Security for Rabin/Williams Signatures.

One of the most interesting ideas in cryptography in the last few years is the search for sound automated proof techniques. I'd like to study a few of the most basic works in this area.

[AbRo] Martin Abadi and Phillip Rogaway. Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption).
[MiWa1] Daniele Micciancio and Bogdan Warinschi. Completeness theorems for the Abadi-Rogaway logic of encrypted expressions.
[MiWa2] Daniele Micciancio and Bogdan Warinschi. Soundness of formal encryption in the presence of active adversaries.

Symmetric cryptography represents 90% of the usage and 5% of the research. I'd like to get a sense of some promising results and directions in this area. Key wrap is one of these.

[RoSh] Phillip Rogaway and Tom Shrimpton. Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Keywrap Problem.
[NIST] NIST key-wrap.

Obfuscation is of very great applied interest, and is only recently beginning to receive a theoretical treatment. The following papers could help lead us into the area.

[BGIRSVY] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, K. Yang. On the (Im)possibility of Obfuscating Programs.
[LyPrSa] Benjamin Lynn, Manoj Prabhakaran and Amit Sahai. Positive Results and Techniques for Obfuscation.

The following paper represents an important advance in our ability to do zero knowledge efficiently and also represents another nice application of pairings. The results have been quite widely applied.

[GrOsSa] Jens Groth, Rafail Ostrovsky and Amit Sahai. Perfect Non-Interactive Zero-Knowledge for NP.

Next are a few representative papers in the area of functional encryption.

[KaSaWa] Jonathan Katz, Amit Sahai and Brent Waters. Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products.
[GoPaSaWa] Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters. Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data.
[OsSaWa] Rafail Ostrovsky, Amit Sahai, and Brent Waters. Attribute-Based Encryption with Non-Monotonic Access Structures.

The next set of papers is concerned with homomorphic encryption and its applications.

[Pa] Pascal Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes.
[BoGoNi] Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. Evaluating 2-DNF Formulas on Ciphertexts.
[OsSk] Rafail Ostrovsky and William Skeith. Private Searching on Streaming Data.

Verifiable file storage is of increasing applied interest. The following represents the state of the art cryptographic solutions.

[ShWa] Hovav Shacham and Brent Waters. Compact Proofs of Retrievability.

The following paper represents new advances in e-cash.

[CHKLM] Jan Camenisch, Susan Hohenberger, Markulf Kohlweiss, Anna Lysyanskaya, and Mira Meyerovich. How to Win the Clone Wars: Efficient Periodic n-Times Anonymous Authentication.