In this seminar, we will discuss current topics in (theoretical) cryptography.

• The talks will be on Wednesday, February 8th, starting at 9:00 in F2.425. The participation is mandatory.
• The exemplary talk by Prof. Blömer will be on Thursday, January 12th, 16:15 in F2.211.
• If you want assistance from your supervisor, please contact him.

First meeting

Here, we will present the available seminar topics and you will be asked to choose one.

Introductory talk

Here, we ask you to present an overview of your topic. This should include roughly 15 minutes where you explain the overall topic and your plans for the essay. In the other 15 minutes you should focus on some part of the topic and explain it formally; your supervisor will help you choose this topic (typically the proof of a simple but central theorem or the structure of a larger proof). Usually there is no need for you to prepare slides, but you should have a good plan of what you present on the whiteboard.

Essay structure

We ask you to turn in a skeleton version of your essay that contains section headings and 0 to 3 sentences per section explaining the section's goals. This is purely for your benefit so that you can get early feedback.

Essay version 1

We strongly recommend Version 1 of the essay to be "feature complete", i.e. everything you plan to have in the final essay should be included in this version. This is your chance to get comprehensive feedback on your work.

Exemplary talk by Prof. Blömer

Prof. Blömer will give a talk on a related topic in order to give you an example how your own talk should look like.

Essay version 2

The second version of the essay should incorporate the feedback given for version 1. We will read this version and give feedback again.

Talk structure

We ask you to turn in the structure of your talk. This can be in the form of slides (with sketched content) or textually. We will give feedback for this.

Talk

You will present your topic for all seminar participants and the supervisors. Your talk should last 1h including discussion (so you should plan to talk around 50-55 minutes). 

Essay

Your essay should be 10 to 12 pages. It should be in the style of a scientific paper. If you like, you can use our LaTeX templates as a starting point. 

Talk

Your talk should last 1h including discussion (so you should plan to talk around 50-55 minutes). You will be able to show slides (bring your own laptop with HDMI or VGA or contact your supervisor). The format is 16:9. If you like, you can use one of our templates as a starting point.

The literature linked in this section is freely accessible from the university's network / via VPN.

Securely outsourcing computation: Yao’s garbled circuits

A very powerful tool in modern cryptography are garbled circuits. The idea here is that a user has some function f in the form of a circuit that he wants someone else to be able to compute (we call this party the evaluator). Depending on the context, the evaluator should not learn the function f, the input x, the result f(x), or any combination of these. To achieve this, the user first garbles f and x, and sends both garbled versions to the evaluator. Using these garbled values, the evaluator can produce a garbled output. In the end the user can ungarble the output, which yields the desired function value f(x).

Literature (preliminary): Mihir Bellare and Viet Tung Hoang and Phillip Rogaway: Foundations of Garbled Circuits

Oblivious RAM - definitions and lower bounds

A sequence of data accesses can provide useful information on the data that is being accessed, e.g. relations between encrypted data items. An observer learning these relations violates the goal of confidentiality we try to achieve using encryption. Oblivious RAM is a technique to establish confidentiality on a larger scale, when compared to simple encryption, by hiding the data access pattern.

Literature: O. Goldreich, R. Ostrovsky: Software protection and simulation on Oblivious RAMs

Path ORAM

A sequence of data accesses can provide useful information on the data that is being accessed, e.g. relations between encrypted data items. An observer learning these relations violates the goal of confidentiality we try to achieve using encryption. Oblivious RAM is a technique to establish confidentiality on a larger scale, when compared to simple encryption, by hiding the data access pattern.

Literature: E. Stefanov, M. van Dijk, E. Shi, et al. Path ORAM: an extremely simple oblivious RAM protocol

Defining and constructing "best possible" order-preserving encryption

An encryption scheme is order-preserving if for all message m, m', we have that if m < m' then Enc(m) < Enc(m'). Such schemes are popular in practice as they allow storing data encrypted such that a database can still do basic operations like sorting on the encrypted data. On the theoretical side, there is a need to "catch up" with practice and offer security definitions and analyses. In their paper, Boldyreva et al. show that a first "ideal" security definition of order-preserving encryption cannot be efficiently realized. They then give another definition and a concrete efficient construction for it.
The goal of the talk and thesis is to present and discuss their two definitions (and what they mean in practice). Then the goal is to simplify their construction by sacrificing some generality to make it easier to understand. 

Literature: Alexandra Boldyreva and Nathan Chenette and Younho Lee and Adam O’Neill: Order-Preserving Symmetric Encryption

Differential Privacy: Mechanism design and application (1)

Privacy is in todays news and is recognised as a valuable property in economics and computer science. Over the past decade new approaches to privacy-preserving data analysis have been studied. They involve multiple disciplines and the majority of approaches combine formal models, game theory, and economic concerns.
As different databases containing detailed user information are accessible to various agents, the problem of how to define privacy in a meaningful, and mathematically rigorous way becomes more important. Differential Privacy addresses this problem by combining definitions of algorithms and mechanisms suitable for a specific class of analysis. Here the application, mechanism design and privacy has to be considered as a whole.
The goals of the talk and the essay are to give an introduction to Differential Privacy and present one application of the techniques. You have to show the details of at least one corresponding mechanism design (f.i. exponential mechanism, interactive mechanism), including the proof of the privacy bound, in the application part of your work.

Literature: C. Dwork, A. Roth - The algorithmic foundations of differential privacy;
C. Dwork - Differential Privacy: A Survey of Results;
M. M. Pai, A. Roth - 2013 - Privacy and Mechanism Design;
F. McSherry, K. Talwar - 2007 - Mechanism Design via Differential Privacy 

Differential Privacy: Mechanism design and application (2)

Privacy is in todays news and is recognised as a valuable property in economics and computer science. Over the past decade new approaches to privacy-preserving data analysis have been studied. They involve multiple disciplines and the majority of approaches combine formal models, game theory, and economic concerns.
As different databases containing detailed user information are accessible to various agents, the problem of how to define privacy in a meaningful, and mathematically rigorous way becomes more important. Differential Privacy addresses this problem by combining definitions of algorithms and mechanisms suitable for a specific class of analysis. Here the application, mechanism design and privacy has to be considered as a whole.
The goals of the talk and the essay are to give an introduction to Differential Privacy and present one application of the techniques. You have to show the details of at least one corresponding mechanism design (f.i. exponential mechanism, interactive mechanism), including the proof of the privacy bound, in the application part of your work.

Literature: C. Dwork, A. Roth - The algorithmic foundations of differential privacy;
C. Dwork - Differential Privacy: A Survey of Results;
M. M. Pai, A. Roth - 2013 - Privacy and Mechanism Design;
F. McSherry, K. Talwar - 2007 - Mechanism Design via Differential Privacy 

Proving knowledge of a number in a certain range

Zero-Knowledge proofs are a powerfull tool often used in modern cryptographic systems, especially within settings involving many different parties. In such schemes, so called Range Proofs are widely used. With range proofs it is possible to convince a verifier that a prover knows some (secret) number in a pre-defined range [a,b], without telling the verifier the exact value. For example, this technique can be used as age verification, or the adherence to a time limit.
The goal of the talk and thesis is to introduce the concept of range proofs, discuss the security definitions and to present a construction (including the proof of security).

Literature: Jan Camenisch, Rafik Chaabouni, abhi shelat: Efficient Protocols for Set Membership and Range Proofs

Transforming sigma protocols to perfect zero-knowledge protocols

Sigma Protocols are Zero-Knowledge Protocols with special properties. Due to these properties, Sigma protocols can be constructed relatively simple. Nevertheless, their major drawback is their weak security guarantee: in practical settings they are insecure. However, there exist techniques to transform Sigma protocols into concurrent zero-knowledge protocols. The goal of the talk and thesis is to analyze these techniques and to prove the zero-knowledgeness of transformed protocols.

Literature: Ivan Damgård: Efficient Concurrent Zero-Knowledge in the Auxiliary String Model

"I know some of these": Proofs of partial knowledge

In modern cryptography, often one party needs to convince another party that they know some secret/solution to an NP question (without revealing the solution itself) - for example for authentication. A useful class of such protocols are so-called Sigma protocols. Sigma protocols can be efficiently composed to "partial proofs of knowledge", allowing to prove statements like "from these three questions I know at least two answers" (without revealing which ones).
The goal of the talk and the essay is to explain the construction for proofs of partial knowledge and to prove that the result preserves the useful properties of sigma protocols.

Literature: Ronald Cramer, Ivan Damgård, Berry Schoenmakers: Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols