COMS E6998-2:  Advanced Cryptography

Spring 2004

Due Dates

• Project Proposal: 3/8 14:00 EST
• Progress Report: 3/31 16:00 EST
• Project: 4/25 (if progress report not on time)
• Project: 5/2 (if progress report on time)

Proposal

The proposal should include the area that you want to investigate, the papers that you plan to read to that end, and your goals for the project. At this stage your goals may be vague and broad, though if you have very specific goals in mind, please include them in the proposal.

The scope (e.g how many papers have been published in the area to date, how many papers you need to read and understand for your project, and in what depth) may vary considerably, though we will try to guide students towards comparable amounts of work to complete the project.

In the second stage you will have to specify your goals much more clearly, typically in the form of a specific research problem you wish to resolve. Outline your planned approach towards satisfying these goals based on the progress you have made by studying the area. Your final project will have to be in-depth research into a well-defined problem (suggesting the problem and making it well defined is part of your job, though you're allowed and encouraged to discuss your ideas with the instructor).

Please notify us of your general area of choice as soon as you can. Several of the suggestions below can support more than one group (working on different subareas), but if several groups consider projects that overlap too much, the first group to request it will get priority.

For all the areas below, contact us for pointers to the important/latest papers in the area.

Project Suggestions (in no particular order:)

• Zero Knowledge: Several advanced topics in zero-knowledge can form the basis for a project. For example, zero-knowledge proofs of knowledge, non-interactive zero-knowledge, non-black-box zero-knowledge, concurrent zero-knowledge, etc.
• Chosen-ciphertext security for public key encryption
• Reductions and completeness in secure computation
• A universal composability framework for secure multi-party computation
• The random oracle model
• Quantum cryptography
• Private information retrieval
• Threshold cryptography
• Secret sharing
• Deniable encryption
• Exposure resilient cryptography
• Privacy preserving data mining
• Anonymity and credential systems
• Algorithmic tamper-proof security
• Pairing-based cryptography
• Identity based encryption (this is currently a subset of the topic above)
• Steganography
• Digital signatures with special properties (e.g. proxy-signatures, aggregate signatures, blind signatures, chameleon signatures, signcryption, forward-secure signatures, group signatures, etc...)
• Incremental cryptography (encryption/hashing)
• Byzantine agreement
• Pseudo-free groups (see the recent paper of Rivest introducing this topic at http://theory.lcs.mit.edu/~rivest/publications.html)
• Formal methods in cryptography.
• Verifiable random functions
• Implementation of huge random objects (see http://www.wisdom.weizmann.ac.il/~oded/p_toro.html)
• Circular encryption
• Zero-knowledge sets / databases
• Average case cryptography / lattices in cryptography

• Micropayments
• Game theory and cryptography
• Secure computation of approximations