Achtung:

Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

AG Codes and Kryptographie Bildinformationen anzeigen

AG Codes and Kryptographie

Oberseminar Codes und Kryptographie

Termine

Das Seminar findet üblicherweise Mittwochs um 14:00 s.t. in Raum F2.425 statt. Für eventuelle Abweichungen bitte Vortragsankündigung beachten. Wenn Sie zusätzlich über die Vorträge per Email informiert werden möchten, melden Sie sich bitte bei Fabian Eidens per Mail.

Vorträge WS 2017-18

22.11.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 k-means problem is APX-hard 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 k-means cost is a meaningful clustering problem if and only if it is worth minimizing the k-means cost. In other words, in order to define a practical k-means clustering problem, we have to incorporate some bias, i.e. domain knowledge. This aspect is not taken into account in the traditional worst-case analysis. It is still an open problem how to describe meaningful k-means instances and how fast the k-means 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 worst-case analysis, should be difficult.  In this talk, I'll give an overview of some of this literature. 

07.11.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 NP-complete. 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 well-known 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.

Vorträge SS 2017

30.08.2017: Johannes Blömer - Lattices and Hashing
23.08.2017: Kathrin Bujna - Sampling-Techniken aus ”Fast and Provably Good Seedings for K-Means” (NIPS 2016)
16.08.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.

19.07.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 Diffie-Hellman Problem, and related problems. That means, every algorithm against Diffie-Hellman-related problems has to solve the Discrete Logarithm Problem directly, unless it relies on inherently non-algebraic 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.

12.07.2017: Fabian Eidens - Generic Construction of Attribute-Based Signatures by Maji et al.

Attribute-based signature (ABS) schemes and a first experiment-basedsecurity definition were introduced by Maji, Prabhakaran and Rosulek [1].The concept of attribute-based signatures considers several signers and an authority that issues secret keys to them. The secret keys encode a set of attributes.Attribute-based 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 attribute-based 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,non-interactive 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.: Attribute-based signatures. CT-RSA 2011. LNCS, vol. 6558. Springer (2011)

31.05.2017: Jan Bobolz - Short arguments are (probably) not convincing - The impossibility of SNARGs from falsifiable assumptions

For NP-languages, we know that there are polynomial-size witnesses for every word that allow a polynomial-time verifier to convince himself of language membership. The question we are concerned with is whether we can make witnesses shorter.

Succinct non-interactive 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 polynomial-time 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 black-box reduction to any falsifiable assumption. Effectively, this rules out SNARGs under standard assumptions with non-revolutionary security proof techniques. In the talk, we are going to present their proof and discuss implications.

[1] Gentry, Craig, and Daniel Wichs. "Separating succinct non-interactive arguments from all falsifiable assumptions." Proceedings of the forty-third annual ACM symposium on Theory of computing. ACM, 2011.

24.05.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.

Vorträge SS 2016 - WS 2017

22.02.2017: Rafael Kurek - Continuous Collision Resistance and its Applications

We introduce a new, simple and non-interactive complexity assumption for cryptographic hash functions, which seems very reasonable for standard functions like SHA-3. We describe how this assumption can be leveraged to obtain standard-model constructions that previously seemed to require a programmable random oracle: a generic construction of identity-based key encapsulation (ID-KEM) with full adaptive security from a scheme with very weak security (“selective and non-adaptive chosen-ID security”), a similar generic construction for digital signatures, and the first constructions of ID-KEMs 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.

22.02.2017: Tibor Jager - 0-RTT 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 0-RTT protocols, a class of KE protocols which allow a client to send cryptographically protected payload in zero round-trip time (0-RTT) 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 0-RTT 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 non-ephemeral 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 0-RTT 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 identity-based key encapsulation scheme.

16.02.2017: Jakob Juhnke - Linkability in Group Signature-based 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 one-way functions and of certain obfuscation schemes.

11.01.2017: Jan Bobolz - Attribute-based 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 state-of-the-art delegatable credential systems. Then we are going to discuss attribute-based delegatable credential systems, which allow very fine-grained management and delegation of access rights. 

21.12.2016: Gennadij Liske - Subtleties in the Semantic Security Definitions for Predicate Encryptions

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.: Semantically-secure functional encryption: Possibility results, impossibility results and the quest for a general definition. In: Abdalla, M., Nita-Rotaru, 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.) Public-Key Cryptography - PKC 2013 - 16th International Conference on Practice and Theory in Public-Key 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).

14.12.2016: Fabian Eidens - Attribute-based Signatures

Attribute-based Signatures were first introduced as a natural extension to Digital Signatures, where the messages are interpreted as attributes from a pre-defined set.
Over the years a much stronger and more general model of Attribute-bases Signatures has been developed. Today the term Attribute-based 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 pre-defined 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)

07.12.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.

30.11.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)

16.11.2016: Sascha Brauer - The Complexity of Swap-Based Local Search for Discrete K-Means and Related Problems

K-means is one of the most widely used clustering objectives. Its most used local search heuristic, the K-means algorithm, is known to have exponential worst-case running time and to produce arbitrarily bad solutions. Kanungo et al. proved that an alternative, swap-based, local search approach yields an O(1) approximation to the K-means problem.

In this talk, we present the basics of the class PLS and the complexity classification of local search problems. We show that swap-based local search for K-Means and similar problems is so-called tightly PLS-complete, which means that these algorithms also have exponential worst-case running time.

(The talk will be held in German)

02.06.2016: Kathrin Bujna - Spektrales Clustering

Spektrale Clustering Methoden sind in der Lage, Muster zu erkennen, an denen die traditionellen Clustering-Algorithmen, wie z.B. der  K-Means 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 Min-Max-Conductance Clustering Problem (auf speziellen Instanzen) tatsächlich (beweisbar) gut funktioniert. 

[1] Peng R., Sun H., Zanetti L.: Partitioning Well-Clustered Graphs: Spectral Clustering Works!, COLT 2015

11.05.2016: Sascha Brauer - The Tempo of K-Means

Die Laufzeit des K-Means 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 K-Means 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 K-Means Algorithmus auf hochdimensionalen Datensätzen.

27.04.2016: Jakob Juhnke - Structure-Preserving Signatures

In vielen kryptographischen Systemen werden Signaturen mit Nicht-Interaktiven Zero-Knowledge Beweisen (NIZK) kombiniert. Für Sicherheitsbeweise wird dabei häufig auf das Random-Oracle-Modell zurück gegriffen. Ein Grund dafür ist, dass es bisher kein im Standardmodell sicheres NIZK-Verfahren gibt, welches mit klassischen digitalen Signaturen kombiniert werden kann.

Mit Structure-Preserving Signatures (SPS) wurden jedoch digitale Signaturen definiert, welche spezielle algebraische Eigenschaften aufweisen. Diese Eigenschaften ermöglichen eine Kombination der Signaturen mit Groth-Sahai-NIZK Beweisen (GS-NIZK), welche im Common Reference String Modell (CRS) sicher sind.

Im Oberseminar sollen SPS und die Verbindung mit GS-NIZK demonstriert und diskutiert werden.

30.03.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 file---the access pattern---can 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.

16.03.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.

09.03.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.

Die Universität der Informationsgesellschaft