What do I learn?

Cryptography is an active field of research. Specifically in the last 5-10 years tremendous breakthroughs have been achieved.

One example is computation over encrypted data. Suppose a client like a smart phone wishes to outsource a computational task to an all-powerful cloud. As an example think of editing a document in the cloud. Clearly the client may send the data (to be edited) in clear to the cloud. However this way the cloud learns the data. While cloud computing is an amazing paradigm, many stakeholders hesitate to move their IT to the cloud. Among the reasons is the lack of privacy. A honest-but-curious cloud provider could simply access information-sensitive data like patents, contracts or staff records. Obviously what one would rather like is a technology where the data is kept private (=encrypted), nevertheless the cloud can do any computation over the data (=evaluatable). Sounds like magic, doesn't it? But contemporary cryptography can do the magic. Encryption schemes with such a magical property are deemed fully homomorphic. It has been an open question in cryptography for more than 25 years whether it is possible to evaluate any function over encrypted data, which was recently answered in an affirmative way. Since the breakthrough researchers have made great steps forward to making fully homomorphic encryption systems suitable for practical applications. Yet it is still a vibrant on-going challenge.

Let's continue with a different problem. Suppose the cloud computed in a magic way a function over the encrypted data. Now we are left with the question whether the cloud did the computation correctly. Computers may err, right? They may loose data due to fault intolerance. One may argue the client should simply compute the function over the data itself and verify the outputs. But wait! If the client can compute the function alone, why should it outsource the computation? Here we're particularly interested in settings where the computational task is heavy in terms of time and/or space resources such that a client cannot carry out the computation itself. As an example now try to think of brute-forcing a hash function or searching for a name in all social networks. Frankly the client is incapable of verifying the correctness of the output. So what the client would like is some guarantee of computation in form of a proof. A fundamental result in contemporary cryptography is that verification of a proof (of computation) can be done more efficiently than the plain computation. More magically, the celebrated PCP theorem says it suffices to probe three bits of a proof string to obtain the sufficient insurance a computation is correct. Sounds like the ideal receipt for the client, doesn't it?

It is this kind of cryptographic magic we want to explore in the course. The workshop-style course is devoted to study recent advances in cryptographic research. We make a pass through the proceedings of top tier cryptography conferences, choose the hot topics and discuss the papers. A list of preliminary topics may, but is subject to student interest, include

  • Contemporary Encryption: Fully homomorphic, functional, constrained
  • Proof Systems: succinct, non-interactive, probabilistically checkable
  • Cryptographic Obfuscation: input indistinguishable, differing-input
  • Tools: multi-linear maps, lattices, dual spaces

What can I do with this knowledge?

You will get to know the magic and ingenuity of cryptographic research. You understand very powerful primitives going far beyond the capabilities of encryption and hash functions. In fact you will understand concepts that pave the ground to carry out your own research. This is the seminal step towards a master thesis, a PhD program, or your own startup. We'll definitely scratch topics influencing the theory and practice of future information security.

Rules of the Game

You are given weekly reading assignments that shall prepare you for the class. You get an oral grade for your active engagement. Much emphasis during the workshop is put on your own ideas. You have to critically put in question current research results and discuss how to improve their weaknesses. After the class you are asked to summarise the findings. For your weekly short paper you get a written grade. The final grade is derived from the weighted oral and written average grades

final grade := 0.5 * (average oral grade) + 0.5 * (average written grade)

The goal of the workshop is to stipulate your own research ideas and condense them into ideally a full paper, meeting the quality requirements to be submitted to a conference. To empower critical thinking and creativity, authors are given the opportunities to work out some bonus:

Incentive#1: Each week the author of the best paper will be awarded. The author is invited to publish an abbreviated version of his paper in the blog and may skip writing one short paper.

Incentive#2: A student with an interesting idea may ask for some extra time to work out the idea (e.g. implement a prototype, prove security, conduct some experiment). The author may skip writing at most half of the short papers (subject to prior agreement), but needs to deliver a full paper at the end of the workshop.

Recommended Conferences

 

The International Association for Cryptographic Research (IACR) organizes several conferences in the theory and practice of cryptography, including TCC, Eurocrypt, Crypto, Asiacrypt, and PKC. Papers to be presented at these conferences regularly appear as pre-print versions on the IACR eprint archive.

Research Papers

  • Adriana Lopez-Alt and Eran Tromer and Vinod Vaikuntanathan: On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption. STOC, 2012
  • Nir Bitansky and Ran Canetti and Alessandro Chiesa and Shafi Goldwasser and Huijia Lin and Aviad Rubinstein and Eran Tromer: The Hunting of the SNARK. ITCS, 2012
  • Rosario Gennaro and Craig Gentry and Bryan Parno and Mariana Raykova: Quadratic Span Programs and Succinct NIZKs without PCPs. EUROCRYPT, 2013