Research Seminar: Codes and Cryptography
Dates
The seminar usually takes place Wednesday 2 p.m. s.t. in F2.425. For possible changes please refer to the official announcement email.
Talks WT 201819
 11/22/2018: Nils Löken  Authenticated Data Structures: Sets and Dictionaries

Sets and dictionaries are data structures commonly found in applications. In this talk, we will discuss authenticated sets and dictionaries that can be used if the data structures need to provide cryptographic guarantees. Particularly, the data structures we present can be stored on untrusted servers. Yet, they guarantee that the server cannot remove elements from the data structures.
In contrast to common authenticated data structures, the data structures we present do not require the source of the data to be trusted.  11/15/2017: Jan Bobolz  What's new? Updates on Anonymous Credentials

Anonymous credentials allow users to prove possession of access rights without revealing their identity. In this talk, we'll cover some recent results for anonymous credentials and applications. In particular, we'll look at the new notion of updatable credentials (unpublished work by Blömer, Bobolz, Eidens).
Updatable credentials are parameterized by attributes. The credential's issuer can apply an update to these attributes without learning anything about the original attributes (hence preserving the credential holder's anonymity). While interesting on its own, we use this property to construct a privacypreserving incentive system.
Incentive systems allow customers to incrementally gather points to spend on bonus items (in Germany, this was popularized by "Payback").
In our construction, users store their points in form of a credential with a "points" attribute. To issue k additional points, the provider can run a "+k" update on this attribute without learning anything about the user's identity or their point count. The major challenge for such systems is doublespending prevention, which will be explained in the talk.  11/08/2018: Sascha Brauer  Coresets for Fuzzy KMeans and their Applications

The fuzzy Kmeans problem is a popular generalization of the wellknown Kmeans problem to soft clusterings.
In this talk, we present the first coresets for fuzzy Kmeans with size linear in the dimension, polynomial in the
number of clusters, and polylogarithmic in the number of points. We further discuss applications of these coresets:
the computation of a (1+\epsilon)approximation for fuzzy Kmeans and how to maintain a coreset in an
insertiononly streaming setting, where data points arrive onebyone.This talk is a long version of the one I will hold at ISAAC 2018.
Talks SS 2018
 07/26/2018: Johannes Blömer  Fully Homomorphic Signatures

We present the Gorbunov, Vaikuntanathan, Wichs construction of fully homomorphic signatures. The construction supports arithmetic circuits of arbitrary but fixed lengths. The signatures are built from a new primitive called homomorphic trapdoor functions. We discuss the connection between homomorphic signatures and homomorphic trapdoor functions. Finally, we show how to construct secure homomorphic trapdoor functions using lattices and assuming the hardness of the SIS problem (small integer solutions).
 07/19/2018: Jakob Juhnke  An Equivalence Between AttributeBased Signatures and Homomorphic Signatures

In AttributeBased Signatures an authority can generate signing keys
related to a set of attributes. These keys can be used to sign messages
if and only if the related attributes satisfy a predefined policy.
Anybody can verify the signature using public parameters to become
convinced that the signer's attributes satisfied the policy without
knowing the attributes. The security requirements are unforgeability of
signatures and key privacy (signatures should not expose the specific
signing key and attributes used).
In homomorphic signatures, a user signs some large data x using the
secret signing key and stores the signed data on a server (the data x
and the signature s). The server can then run some computation y=g(x) on
the signed data and homomorphically produce a short signature s'.
Anybody can verify the signature s' using the public verification key
and become convinced that y is the correct output of the computation g
over the user's data x, without needing to have the underlying data
itself. A secure homomorphic signature scheme must be unforgeable and
context hiding (a signature which certifies y as the output of some
computation g over the user's data should not reveal anything about the
underlying data beyond the output of the computation).
Recently, Rotem Tsabary presented an equivalence between attributebased
signatures and homomorphic signatures (TCC 2017). Unfortunately, Tsabary
uses weaker security notions than the standard notions to prove the
equivalence. In this talk we discuss his results and point out some
subtleties in his construction which must be fixed to use
attributebased signatures and homomorphic signatures equivalently.  07/12/2018: Nils Löken  Computing on Authenticated Data  Homomorphic Signatures

When computing on authenticated data it can be useful to make results available to an audience that is unaware of the source data, and should not learn anything about the source data beyond what is revealed by the result. However, receivers of the result should be able to verify the result.
Homomorphic signatures allow the derivation of signatures on the result from signatures on the inputs. Receivers of the result can then check the signature on the result and be assured that the result was computed from authenticated data originating from a given source.
In my talk, I will present relevant security notions and several simple, yet useful homomorphic signature schemes.
 06/28/2018: Jan Bobolz and Alexander Setzer  Provably Anonymous Communication Based on Trusted Execution Environments

We investigate the use of trusted execution environments (TEEs, such as Intel's SGX) for an anonymous
communication infrastructure over untrusted networks. For this, we present the general idea of
exploiting trusted execution environments for the purpose of anonymous communication, including
a continuoustime security framework that models strong anonymity guarantees in the presence
of an adversary that observes all network traffic and can adaptively corrupt a constant fraction of
participating nodes. In our framework, a participating node can generate a number of unlinkable
pseudonyms. Messages are sent from and to pseudonyms, allowing both senders and receivers of
messages to remain anonymous. We introduce a concrete construction, which shows viability of
our TEEbased approach to anonymous communication. The construction draws from techniques
from cryptography and overlay networks. Our techniques are very general and can be used as a
basis for future constructions with similar goals.
In this talk, we outline our construction and the main technical ideas used in our work. We supplement
this by an overview of Intel SGX and describe how we implemented a prototype of our anonymous
communication infrastructure using SGX.  06/21/2018: Fabian Eidens  Protocol Zoo: ZAPs of knowledge and his friends

Our goal is to get an efficient protocol for anonymous identification that also supports an interesting class of statements. An NP relation R where R(x,w) = true for statement x and witness w is the ultimate goal for so called proof systems used for anonymous identification. There is a zoo of proof systems: zeroknowledge proofs of knowledge, witness indistinguishable proofs, noninteractive proofs, SNARK, subversionresistant proofs, ZAPS, and so on.
ZAPs are noninteractive witnessindistinguishable proofs without any setup. This is a big step towards practical applications, since the often used proofs system like GrothSahai proofs (GSproofs) are only secure under a trusted setup.
We present the recent work by Fuchsbauer and Orrù "Noninteractive zaps of knowledge" and use this as a starting point give an overview of existing proof systems, their features and varieties. Fuchsbauer and Orrù show the first ZAP that satisfies the strong soundness definition called "argument of knowledge". An argument of knowledge proves that not only the statement is true, but also that the prover knows a witness for it.
 06/04/2018: Sascha Brauer  Structural Similarity of Good KMeans Solutions

The classical Kmeans problem is solved by minimizing a sumofsquares error term. This objective function does not encompass any structural information about the solution. It is easy to formulate criteria, such that solutions which are structurally similar to an optimal solution have an almost optimal objective value. However, the reverse direction is not clear. In this talk we have a look at a short string of work by Marina Meilă in which she formulates sufficient conditions, such that a solution with small enough cost is structurally similar to an optimal solution. These conditions are useful in practice, since they can be evaluated using only the data set and a single solution, without any additional assumptions.
Talks WT 201718
 01/25/2017: Johannes Blömer  Coppersmith’s Attack on Widely Used RSA Moduli

I present the recent result that RSA moduli generated by a popular cryptolib are insecure. The attack on these RSA moduli is based on 20 year old results by Coppersmith and others. In the talk I will use Coppersmith’s method as a black box and will concentrate on the basics of the attack and the techniques to achieve a practical attack.
 01/17/2018: Nils Löken  Forklinearizability

Sharing untrusted memory among multiple users is rather common. We discuss some security guarantees that can be achieved on such memory, particularly, the notion of forklinearizability. Forklinearizability does not prevent dishonest behaviour of untrusted memory, but makes it easily observable. The notion of forklinearizability can be achieved through various means, for example blockchains, and can be applied to a lot of application scenarios, like an authenticated SVN repository or allowing multiple data sources to jointly maintain an authenticated data structure in a generic way.
 01/10/2018: Jan Bobolz  Signature Schemes based on Algebraic Trickery

In this talk we are going to explore a semiarbitrary collection of useful algebraic tricks for the construction of cryptographic schemes (in particular, but not limited to, signature schemes).
For this, we are going to take a look at three topics:
(1) Waters signatures/IBE and a programmable hash function
(2) PointchevalSanders signatures based on a new noninteractive assumption (improvement over the original paper)
(3) Signatures on vector spaces and their applications to network codingThese schemes have in common that their proofs provide the "ah, okay, this term just vanishes" effect. We are going to try to highlight what algebraic design decisions lead to those convenient "coincidences"; hopefully supplying you with a small toolbox of tricks for your future algebraic crypto constructions.
 12/13/2017: Fabian Eidens  Signatures of Knowledge from SimulationExtractable Succinct Noninteractive Arguments of Knowledge  SESNARK

Signatures of Knowledge (SoK) are used in many cryptographic systems like Reputation Systems, Group Signatures and Ring Signatures. We know how to build them using the so called FiatShamir transformation in the RandomOracle model. There is also a UC secure construction in the standard model utilising publickey encryption. In the talk we will present the work by Groth and Maller. They introduce a construction of SoKs from simulationextractable succinct noninteractive arguments of knowledge (SESNARK). Their construction yields a SoK consisting of only 3 group elements and they prove that this is optimal for pairingbased SoKs.
We will concentrate on the construction of the SoK given a SESNARK and highlight their relation. A part of this talk will be the introduction of simulationextractability.
 12/06/2017: Jakob Juhnke  KeyHomomorphic Signatures and their Applications

Recently, Derler and Slamanig introduced KeyHomomorphic Signatures. Such Signatures are a generalization of larger classes of existing signature schemes and can be used to build other interesting primitives (ring signatures, multisignatures, simulation sound extractable arguments of knowledge, and others) in a simple and elegant way. In this talk we will present different formal definitions of KeyHomomorphic Signatures and discuss the application to arguments of knowledge in detail.
 11/22/2017: Kathrin Bujna  Theoretical Understanding of Clustering

There is a vast number of theoretical results that seems to indicate that clustering is extremely difficult. For instance, we know that the kmeans problem is APXhard and there is even an "Impossibility Theorem for Clustering". However,"clustering" cannot be defined precisely; it's in the eye of the beholder. Which is bascially why there are so many different clustering algorithms, clustering "problems", and no general clustering theory. Besides that, in practice, we observe that simple heuristics (often) find meaningful results.
For instance, the problem of finding a clustering that minimizes the kmeans cost is a meaningful clustering problem if and only if it is worth minimizing the kmeans cost. In other words, in order to define a practical kmeans clustering problem, we have to incorporate some bias, i.e. domain knowledge. This aspect is not taken into account in the traditional worstcase analysis. It is still an open problem how to describe meaningful kmeans instances and how fast the kmeans problem can be solved with respect to these instances.
There is a growing amount of literature that deals with this idea and shows that there are provably accurate and efficient algorithms for clustering problems that, according to traditional worstcase analysis, should be difficult. In this talk, I'll give an overview of some of this literature.
 11/07/2017: Sascha Brauer  Parameterizing Graph Problems

Solving problems on graphs is the heart of theoretical computer science (admittedly, this is an overly dramatic statement, but you get the drift ;)). However, a whole lot of interesting and practically relevant graph problems turn out to be NPcomplete. Naturally, one might ask the question: can we restrict the input space to allow for efficient algorithms?
In parameterized complexity theory, we detach certain parts of the input (the parameter) from the size of the given instance. The goal is to find efficient algorithms, assuming the parameter is some small constant.
In this talk, we discuss different, clearly quantifiable, parameterizations of wellknown graph problems. We further show negative and positive results of these parameterization in the context of parameterized complexity. If time permits we discuss applications of these techniques to certain graph variants of clustering problems.
Talks SS 2017
 08/30/2017: Johannes Blömer  Lattices and Hashing

 08/23/2017: Kathrin Bujna  SamplingTechniken aus ”Fast and Provably Good Seedings for KMeans” (NIPS 2016)

 08/16/2017: Sascha Brauer  A Gentle (?) Introduction to Differential Privacy

Companies gathering huge amounts of information sometimes release small snapshots of their data, either to promote research or posing some sort of "challenge" resulting in monetary gain.
Time and time again such companies have impressed us with their disability to anonymize these datasets.
But are we actually able to make sure that a dataset is anonymized?
Or rather, how do we determine "how much" anonymization is necessary?In her seminal work, Cynthia Dwork defined the field of Differential Privacy, with the goal to formalize the risk of including sensitive information into publicly available datasets. In this talk, we explore the formal fundamentals of Differential Privacy and present basic tools (quantifiably) anonymizing datasets.
 07/19/2017: Jakob Juhnke  An Introduction to the Algebraic Group Model

The Generic Group Model (GGM) is often used to analyze new cryptographic hardness assumption and/or primitives. In the GGM algorithms are only allowed to evaluate group operations using designated oracles; adversaries cannot make use the representation of the groups used in practice. To overcome this limitation, Kiltz and Loss recently proposed the Algebraic Group Model (AGM). In this model, an adversary A is modeled as "algebraic": whenever A outputs some group element Z, it also has to output a representation of Z with respect to all group elements given to A so far. Using algebraic algorithms, Kiltz and Loss prove the equivalence of the Discrete Logarithm Problem to the DiffieHellman Problem, and related problems. That means, every algorithm against DiffieHellmanrelated problems has to solve the Discrete Logarithm Problem directly, unless it relies on inherently nonalgebraic operations.
In this talk we will give a short introduction to the AGM, and we will show how to analyze new hardness assumption in this model.  07/12/2017: Fabian Eidens  Generic Construction of AttributeBased Signatures by Maji et al.

Attributebased signature (ABS) schemes and a first experimentbasedsecurity definition were introduced by Maji, Prabhakaran and Rosulek [1].The concept of attributebased signatures considers several signers and an authority that issues secret keys to them. The secret keys encode a set of attributes.Attributebased signatures are generated on a message and a policy, for example aBoolean formula over the attributes. To generate a valid signaturea signer has to possess a secret key where the encoded attributessatisfy the given policy. A receiver of an attributebased signatureis able to verify whether it was generated by a signer that has satisfyingattributes for the given policy. The validity of a signature is thereforenot bound to a single signer's identity but rather to a group of signerswith satisfying attributes.
A secure ABS is defined as unforgeable and perfectly private. Unforgeabilitycaptures that a valid signature on a message and policy should onlybe generated by a single signer whose secret key encodes attributesthat satisfy the policy and not by colluding signers. Prefect privacycaptures that a signature is independent of the secret key used togenerate it. This means that a signature itself tells a verifier nothingabout the identity of the signer or the concrete attributes used togenerate the signature.
The generic construction presented in [1] is based on digital signatures,noninteractive witness indistinguishable proofs, and monotone span programs.We will present a simplified version of the construction in respect to a stronger security model.
[1] Maji, H.K., Prabhakaran, M., Rosulek, M.: Attributebased signatures. CTRSA 2011. LNCS, vol. 6558. Springer (2011)
 05/31/2017: Jan Bobolz  Short arguments are (probably) not convincing  The impossibility of SNARGs from falsifiable assumptions

For NPlanguages, we know that there are polynomialsize witnesses for every word that allow a polynomialtime verifier to convince himself of language membership. The question we are concerned with is whether we can make witnesses shorter.
Succinct noninteractive arguments (SNARGs) promise witnesses of sublinear length. For SNARGs, we weaken the strong notion of a proof (there are no proofs for false statements) to arguments (there may exist arguments for false statements, but they are hard to find for any polynomialtime bounded adversary). There are several constructions of SNARGs for (probably) hard languages, but none of them are proven secure under any of the standard hardness assumptions in cryptography.
The lack of such constructions is explained by Gentry and Wichs [1]. They showed that no SNARG can be proven secure with a blackbox reduction to any falsifiable assumption. Effectively, this rules out SNARGs under standard assumptions with nonrevolutionary security proof techniques. In the talk, we are going to present their proof and discuss implications.
[1] Gentry, Craig, and Daniel Wichs. "Separating succinct noninteractive arguments from all falsifiable assumptions." Proceedings of the fortythird annual ACM symposium on Theory of computing. ACM, 2011.
 05/24/2017: Nils Löken  Bloom filters and their application security

Bloom filters have found widespread use for answering set (non)membership queries in a variety of application types. Examples include spell checking, cache management for network caches, and recognizing malicious URLs. Due to the use of Bloom filters in security critical applications, the quersion arises how Bloom filters affect the applications' security. In the talk, we will present Bloom filters and potential attacks on them.
Talks ST 2016  WT 2017
 02/22/2017: Rafael Kurek  Continuous Collision Resistance and its Applications

We introduce a new, simple and noninteractive complexity assumption for cryptographic hash functions, which seems very reasonable for standard functions like SHA3. We describe how this assumption can be leveraged to obtain standardmodel constructions that previously seemed to require a programmable random oracle: a generic construction of identitybased key encapsulation (IDKEM) with full adaptive security from a scheme with very weak security (“selective and nonadaptive chosenID security”), a similar generic construction for digital signatures, and the first constructions of IDKEMs and signatures over bilinear groups, where a ciphertext or signature consists of only a single group element and which achieve full adaptive security without random oracles.
 02/22/2017: Tibor Jager  0RTT Key Exchange with Full Forward Secrecy

Reducing latency overhead while maintaining critical security guarantees like forward secrecy has become a major design goal for key exchange (KE) protocols, both in academia and industry. Of particular interest in this regard are 0RTT protocols, a class of KE protocols which allow a client to send cryptographically protected payload in zero roundtrip time (0RTT) along with the very first KE protocol message, thereby minimizing latency. Prominent examples are Google's QUIC protocol and the upcoming TLS protocol version~1.3.
Intrinsically, the main challenge in a 0RTT key exchange is to achieve forward secrecy and security against replay attacks for the very first payload message sent in the protocol. According to cryptographic folklore, it is impossible to achieve forward secrecy for this message, because the session key used to protect it must depend on a nonephemeral secret of the receiver. If this secret is later leaked to an attacker, it should intuitively be possible for the attacker to compute the session key by performing the same computations as the receiver in the actual session.
In this paper we show that this belief is actually false. We construct the first 0RTT key exchange protocol which provides full forward secrecy for all transmitted payload messages and is automatically resilient to replay attacks. In our construction we leverage a puncturable key encapsulation scheme which permits each ciphertext to only be decrypted once. Fundamentally, this is achieved by evolving the secret key after each decryption operation, but without modifying the corresponding public key or relying on shared state.
Our construction can be seen as an application of the puncturable encryption idea of Green and Miers (Oakland 2015). We provide a new generic construction of this tool that can be instantiated with any selectively secure hierarchical identitybased key encapsulation scheme.
 02/16/2017: Jakob Juhnke  Linkability in Group Signaturebased Applications

Mit Hilfe von Gruppensignaturen können Mitglieder einer Gruppe anonym
Nachrichten signieren. Lediglich eine spezielle Partei, der
Gruppenmanager, ist in der Lage, die Identität eines Signierers aus
einer gültigen Signatur zu extrahieren. Somit ist auch nur der
Gruppenmanager fähig zu entscheiden, ob zwei Signaturen vom selben
Signierer erstellt wurden. Diese Fähigkeit wird in praktischen
Applikationen jedoch häufig benötigt, weswegen verschiedene Techniken
entwickelt wurden, welche eine Verknüpfbarkeit von Signaturen ermöglichen.
In diesem Vortrag werden verschiedene Verknüpfungstechniken vorgestellt,
welche nicht nur für Gruppensignaturen relevant sind. Des Weiteren
werden Auswirkungen auf entsprechende Sicherheitsdefinitionen diskutiert.  02/02/2017: Johannes Blömer  Cryptographic hardness of Nash equilibria

We present and discuss recent results which show that under appropriate cryptographic
assumptions Nash equilibria cannot be computed in polynomial time. More generally, the
results show that the class PPAD is not contained in P. The cryptographic assumptions include the
existence of oneway functions and of certain obfuscation schemes.  01/11/2017: Jan Bobolz  Attributebased anonymous credentials with delegation

In anonymous credential systems, there are authorities, users, and verifiers. Users approach an authority, who issues them a credential. A credential certifies a user certain rights (or a certain level of trust), which can be checked by a verifier. These systems are anonymous because the user does not reveal his exact identity to the verifier. Instead, the verifier only learns the identity of the authority who issued the user his credential (and if the verifier trusts this authority's judgement, it will allow the user access).
A natural extension of this concept is that the user is not necessarily granted his rights directly by the authority, but indirectly through a chain of trust. This is realized by delegatable credential systems. That is, the actual authority can issue a (level 1) credential to some other party, enabling that party to issue (level 2) credentials in the authority's name. The second party may further delegate its credential to a third party, enabling it to issue level 3 credentials, etc. This is similar to how TLS certificate chains work. In contrast to TLS certificates, however, a verifier does not learn the specific delegation chain as it may restrict the user's anonymity unncessarily. For example, if the delegation chain is [Telekom](root) > [DFN] > [Paderborn University] > [Specific Student], then all involved parties except the Telekom are hidden from verifiers as any one of them would unnecessarily restrict the anonymity of the authenticating student.
In the talk, I am going to briefly present the ideas behind stateoftheart delegatable credential systems. Then we are going to discuss attributebased delegatable credential systems, which allow very finegrained management and delegation of access rights.
 12/21/2016: Gennadij Liske  Subtleties in the Semantic Security Definitions for Predicate Encryptions

(The talk will be held in German)
Semantische Sicherheit (SS) ist eine intuitive Definition der Sicherheitseigenschaften von Verschlüsselungsverfahren. Während im Falle von herkömmlichen PKE Verfahren Semantische Sicherheit (in unterschiedlichsten Variationen) ist äquivalent zu der einfacheren Ununterscheidbarkeitsdefinition (IND) [1], dies ist nicht der Fall zum Beispiel im Kontext von Prädikatbasierten Verschlüsselungsverfahren (PEs).
Nichtdestotrotz fand die Ununterscheidbarkeitsdefinition eine weite Verbreitung bei PEs während es für die Semantische Sicherheit Unmöglichkeitsergebnisse sogar für die einfachsten und natürlichen Prädikate existieren [2,3,4]. Für die gleichen Prädikate wurde aber auch die Äquivalenz der Ununterscheidbarkeit und der Semantischen Sicherheit gezeigt [5]. Wie ist das möglich?
In diesem Vortrag gehen wir dieser Frage auf den Grund, betrachten verschiedene Varianten die Semantische Sicherheit im Kontext von PEs zu definieren, und zeigen ab wann die Äquivalenz zwischen SS und IND verletzt wird.
[1] The Foundations of Cryptography  Volume 2, Basic Applications. Cambridge University Press 2004.
[2] Boneh, D., Sahai, A., Waters, B.: Functional encryption: Definitions and challenges. In: Ishai, Y. (ed.) Theory of Cryptography  8th Theory of Cryptography Conference, TCC 2011. LNCS, vol. 6597, pp. 253–273. Springer (2011).
[3] Bellare, M., O’Neill, A.: Semanticallysecure functional encryption: Possibility results, impossibility results and the quest for a general definition. In: Abdalla, M., NitaRotaru, C., Dahab, R. (eds.) Cryptology and Network Security  12th International Conference, CANS 2013. LNCS, vol. 8257, pp. 218–234. Springer (2013),
[4] Barbosa, M., Farshim, P.: On the semantic security of functional encryption schemes. In: Kurosawa, K., Hanaoka, G. (eds.) PublicKey Cryptography  PKC 2013  16th International Conference on Practice and Theory in PublicKey Cryptography. LNCS, vol. 7778, pp. 143–161. Springer (2013)
[5] Attrapadung, N., Cui, Y., Galindo, D., Hanaoka, G., Hasuo, I., Imai, H., Matsuura, K., Yang, P., Zhang, R.: Relations among notions of security for identity based encryption schemes. In: Correa, J.R., Hevia, A., Kiwi, M.A. (eds.) LATIN 2006: Theoretical Informatics, 7th Latin American Symposium. LNCS, vol. 3887, pp. 130–141. Springer (2006).
 12/14/2016: Fabian Eidens  Attributebased Signatures

Attributebased Signatures were first introduced as a natural extension to Digital Signatures, where the messages are interpreted as attributes from a predefined set.
Over the years a much stronger and more general model of Attributebases Signatures has been developed. Today the term Attributebased Signatures describes signatures that are computed on messages and attributes, where attributes are separated from messages. In Detail, the attributes are encoded in the signing key and a signature is valid only if the attributes fulfil a predefined policy (e.g., boolean formula).
In this talk we will compare security models and present a concrete scheme.(The talk will be held in German)
 12/07/2016: Nils Löken  Searchable Encryption with Access Control

Searchable encryption is a technology that encrypts data in a way that allows ciphertexts to be searched. We ask how searchable encryption can be achieved in scenarios with multiple users involved, i.e. data sharing. Scenarios where not all users are authorized to access all data are of particular interest to us, because such scenarios ask for means of access control.
The talk will give an introduction to searchable symmetric encryption and how it can serve as a foundation for searchable encryption with access control.
 11/30/2016: Kathrin Bujna  Regressionsanalyse und Gaußprozesse

Bei der Regressionsanalyse geht es grob gesagt darum, Abhängigkeiten zwischen Variablen zu modellieren. Der einfachste Ansatz hierfür ist die einfache lineare Regression, bei der ein explizites Modell bestimmt wird. Sieht man diesen Ansatz im Kontext der Bayesschen Inferenz, wird daraus die sogenannte Bayessche lineare Regression, bei der, grob gesagt, nicht mehr ein einzelnes Modell sondern eine Verteilung über Modelle bestimmt wird, die angibt, wie vernünftig einzelne Modelle die Abhängigkeit jeweils beschreiben. Betrachtet man diesen letzten Ansatz genauer, stellt man fest, dass er auch abstrakter, ohne die Idee von konkreten Modellen, beschrieben werden kann. Das funktioniert mit Hilfe multivariater Gaußverteilungen bzw. deren Verallgemeinerung, den sogenannten Gaußprozessen. Im Vortrag wird ein Überblick über die genannten Verfahren gegeben.
(The talk will be held in German)
 11/11/2016: Sascha Brauer  The Complexity of SwapBased Local Search for Discrete KMeans and Related Problems

Kmeans is one of the most widely used clustering objectives. Its most used local search heuristic, the Kmeans algorithm, is known to have exponential worstcase running time and to produce arbitrarily bad solutions. Kanungo et al. proved that an alternative, swapbased, local search approach yields an O(1) approximation to the Kmeans problem.
In this talk, we present the basics of the class PLS and the complexity classification of local search problems. We show that swapbased local search for KMeans and similar problems is socalled tightly PLScomplete, which means that these algorithms also have exponential worstcase running time.
(The talk will be held in German)
 06/02/2016: Kathrin Bujna  Spektrales Clustering

Spektrale Clustering Methoden sind in der Lage, Muster zu erkennen, an denen die traditionellen ClusteringAlgorithmen, wie z.B. der KMeans Algorithmus, kläglich scheitern würden. Darüber hinaus sind diese Methoden sehr einfach zu implementieren. Der einzige große Wermutstropfen ist die hohe Laufzeit. Nichtsdestotrotz werden mit Hilfe von spektralen Clustering Methoden hochqualitative Ergebnisse auf (kleinen) Datensätzen erreicht.
Warum spektrale Algorithmen überhaupt irgendetwas sinnvolles berechnen, ist erstmal nicht offensichtlich. Darum beschäftigen wir uns im ersten Teil des Vortrags mit einigen grundlegenden Eigenschaften, die das Spektrum spezieller Matrizen mit Clusterings verbinden. Im zweiten Teil des Vortrags geht es dann um ein neues Ergebnis [1], welches besagt, dass ein spezieller spektraler Algorithmus für das MinMaxConductance Clustering Problem (auf speziellen Instanzen) tatsächlich (beweisbar) gut funktioniert.
[1] Peng R., Sun H., Zanetti L.: Partitioning WellClustered Graphs: Spectral Clustering Works!, COLT 2015
 05/11/2016: Sascha Brauer  The Tempo of KMeans

Die Laufzeit des KMeans Algorithmus ist aufgrund seiner hohen praktischen Relevanz immer wieder im Fokus der theoretischen Forschung. Im ersten Teil dieses Vortrags werden wir uns mit einer grundlegenden Idee beschäftigen, die verwendet wurde um zu zeigen, dass die Laufzeit von KMeans schon in zwei Dimensionen exponentiell in der Anzahl Punkte sein kann.
Trotz dieses extrem schlechten Worst Case Verhalten, terminiert der Algorithmus in der Praxis meist recht schnell. Ein Versuch diesen Effekt zu erklären ist die geglättete Analyse. Im zweiten Teil dieses Vortrags beschäftigen wir uns mit den Grundlagen der geglätteten Analyse, und betrachten eine einfache Analyse für den KMeans Algorithmus auf hochdimensionalen Datensätzen.
 04/27/2016: Jakob Juhnke  StructurePreserving Signatures

In vielen kryptographischen Systemen werden Signaturen mit NichtInteraktiven ZeroKnowledge Beweisen (NIZK) kombiniert. Für Sicherheitsbeweise wird dabei häufig auf das RandomOracleModell zurück gegriffen. Ein Grund dafür ist, dass es bisher kein im Standardmodell sicheres NIZKVerfahren gibt, welches mit klassischen digitalen Signaturen kombiniert werden kann.
Mit StructurePreserving Signatures (SPS) wurden jedoch digitale Signaturen definiert, welche spezielle algebraische Eigenschaften aufweisen. Diese Eigenschaften ermöglichen eine Kombination der Signaturen mit GrothSahaiNIZK Beweisen (GSNIZK), welche im Common Reference String Modell (CRS) sicher sind.
Im Oberseminar sollen SPS und die Verbindung mit GSNIZK demonstriert und diskutiert werden.
 03/30/2016: Nils Löken  Oblivious RAM

A sequence of data accesses can provide useful information on the data that is being accessed. If a cloud storage provider sees a couple of files being accessed at about the same time and this pattern is observed several times, with high probability there is a strong relation between the these files' contents. The cloud storage provider can come up with such a conclusion without knowledge of the contents, i. e. even if the files are encrypted.
Ensuring confidentiality is the reason for encrypting files but the above example shows how the context access to an encrypted filethe access patterncan pose a breach of confidentiality. Oblivious RAM addresses the issue of information leakage through access patterns by completely hiding the access pattern.
In the seminar, we will present a lower bound on the costs of oblivious RAM, as well as techniques for constructing oblivious RAM.
 03/16/2016: Fabian Eidens  Short Randomizable Signatures and Sequential Aggregate Signatures

Short signatures impact several applications like Credential Systems, Group Signatures, Reputation Systems and Identification Protocols. Therefore, a new direction in this area is to define signature schemes in the type 3 bilinear group setting. The type 3 setting describes bilinear groups with efficient exponentiation, hashing and pairing. Regarding security and future development of computational power one should only consider the type 3 setting.
Sequential Aggregate Signatures are used in secure route attestation and certificate chains. For example a backbone router wants to advertise the routes which should be used to reach his network. Each router on a routing path adds its signature to a valid route attestation before sending it to its neighbors. Deployed network protocols limit the size of route attestation. Therefore we use aggregate signatures to reduce the overhead of multiple signatures. Interestingly, aggregate signatures can in general be used to shorten certificatie chains.
In the seminar, we will present the mentioned theoretical construction and take a look at the advantages of the approaches.
 03/09/2016: Jan Bobolz  Delegating Computation to Untrusted Parties: Verifiable Computation

Verifiable computation is concerned with the following scenario: Some computationally weak unit V wants to delegate an (expensive) computation of f(x) to an untrusted third party P. After receiving the alleged result y, the weak party V wants to ensure that indeed, y = f(x), without having to redo the computation itself. To facilitate this, P supplies V with a short and efficiently checkable "proof" that y = f(x).
Interestingly, this scenario can be realized for arbitary computable functions f such that proof verification is essentially polylogarithmic in the length of the original computation. Unfortunately, while theoretically interesting, this construction remains far too computationally expensive for practical use. In recent years, cryptography research has been working towards practical verifiable computation.
In the seminar, we will present the mentioned theoretical construction and take a look at modern approaches.