Oberseminar über Kryptographie
CITS » Lehre » Sommersemester 2015

Oberseminar über Kryptographie



Oberseminar
Dozent Zeit Raum Erstmals am
Prof. A. May
Prof. Eike Kiltz
freitags, 10.45-12.00 NA 5/64 10.04.15
Datum Vor­tra­gen­de Per­son Titel Raum­num­mer Be­ginn
10.04 Manuel Fersch Quantum Secure MACs 5/64 10.45 Uhr
08.05 Yida Xu Private Information Retrieval 5/64 10.45 Uhr
10.06 Benedikt Auerbach Optimal Structure-Preserving Signatures in Asymetric Bilinear Groups 5/64 11.00 Uhr
26.06 Marie-Sarah Lacharité Revisiting the security model for BGLS aggregate signatures 5/64 11.00 Uhr
19.06 Gregor Leander Some observation on Simon 5/64 11.00 Uhr
03.07 Jorge Villar Equivalences and Black-Box Separations of Matrix Diffie-Hellman Problems 5/64 11.00 Uhr
10.07 Jiaxin Pan Structure-Preserving Signatures from Standard Assumptions, Revisited 5/64 11.00 Uhr
17.07 Felix Heuer Standard Security Does Imply Security Against Selective Opening for Markov Distributions 5/64 11.00 Uhr

Quantum Secure MACs

Once quantum computers with sufficient computing power can be built, many encryption and authentication schemes that are secure in the world of classical computing can be broken easily.In my master's thesis, I show how to construct MACs that are secure against quantum adversaries, even if there is quantum interaction with the attacker. This is a stronger security notion than the one used in post-quantum cryptography, where the adversary can use a quantum computer for its computations but the interaction with the cryptographic scheme is always classical. In order to achieve this kind of security, I use techniques introduced by Dan Boneh and Mark Zhandry in their paper 'Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World'.

Private Information Retrieval

In this presentation we give a introduction of the private information retrieval. Firstly, we briefly introduce the intention and requirement of PIR. We will also give a introduction of the development of PIR problem by introducing historical significant PIR from Information theoretic PIR with database replication to computational PIR without database replication as well as the later researches of trading off between communication complexity and computational complexity. Then we’ll learn Cachin’s modeling of PIR. Later we give a specified definition of correctness and privacy. We define the privacy of PIR through the indistinguishability of queries. We then construct a novel PIR under phi-hiding assumption and prove it secure.

Revisiting the security model for BGLS aggregate signatures

Aggregate signature schemes combine multiple users' digital signatures on various messages into one fixed-length signature. I'll present the elegant, pairing-based aggregate signature scheme of Boneh, Gentry, Lynn, and Shacham (BGLS), in which anyone can aggregate the signatures in any order. In the original security model, the forger is given one public key to target. In real life, however, a forger knows all signers' public keys. Could the forger have an advantage when it can choose which signer(s) to target? How is the tightness of the security reduction affected by the forger having more power? Using diagrams to illustrate security reductions, I'll compare different types of forgers. Finally, I'll explore how the revised security model affects the recommended group sizes.

Some observations on Simon

I will talk about the NSA block ciphers Simon and Speck. Actually only about Simon. I will explain some initial ideas on how to analyze their resistance against linear and differential attacks.

Equivalences and Black-Box Separations of Matrix Diffie-Hellman Problems

In this talk we provide new algebraic tools to study the relationship between different Matrix Diffie-Hellman (MDDH) Problems. Namely, we provide a purely algebraic criterion to decide whether there exists a generic black-box reduction, and in many cases, when the answer is positive we also build an explicit reduction with the following properties: it only makes a single oracle call, it is tight and it makes use only of operations in the base group. It is well known that two MDDH problems described by matrices with a different number of rows are separated by an oracle computing certain multilinear map. Thus, we put the focus on MDDH problems of the same size. Then, we show that MDDH problems described with a different number of parameters are also separated (meaning that a successful reduction cannot reduce the amount of randomness in the problem instance). When comparing MDDH problems of the same size and number of parameters, we show that surprisingly they are equivalent or incomparable. This suggests that a complete classification into equivalence classes can be done. We give some positive and negative results about equivalence, in particular solving the open problem of whether the Linear and the Cascade MDDH problems are reducible to each other.

Structure-Preserving Signatures from Standard Assumptions, Revisited

Structure-preserving signatures (SPS) are pairing-based signatures where all the messages, signatures and public keys are group elements, with numerous applications in public-key cryptography. We present new, simple and improved SPS constructions under standard assumptions via a conceptually different approach. Our constructions significantly narrow the gap between existing constructions from standard assumptions and optimal schemes in the generic group model. This is a joint work with Eike Kiltz and Hoeteck Wee. The paper will be presented at this year CRYPTO and the full version is on eprint (Report 2015/604)

Standard Security Does Imply Security Against Selective Opening for Markov Distributions

SAbout three decades ago it was realized that implementing private channels between parties which can be adaptively corrupted requires an encryption scheme that is secure against selective opening attacks. Whether standard (IND-CPA) security implies security against selective opening attacks has been a major open question since. The only known reduction from selective opening to IND-CPA security loses an exponential factor. A polynomial reduction is only known for the very special case where the distribution considered in the selective opening security experiment is a product distribution, i.e., the messages are samples independent from each other. In this talk we give a reduction that is polynomial for Markov distributions. This is joint work with Eike Kiltz and Krzysztof Pietrzak.