Oberseminar über Kryptographie
CITS » Lehre » Sommersemester 2014

Oberseminar über Kryptographie

150 909 MSc Mod 5: Modul 5

Oberseminar
Dozent Zeit Raum Erstmals am
Prof. A. May
Prof. Eike Kiltz
donnerstags, 11.00-12.00 NA 5/24 (Zeitraum 04.09.-02.10.2014)
NA 5/64
Datum Vor­tra­gen­de Per­son Titel Raum­num­mer Be­ginn
01.8 Gottfried Herold Polynomial Spaces - A New Framework for Composite-To-Prime-Order Transformations 5/24 16.00 Uhr
07.8 Ilya Ozerov A Generic Algorithm for Small Weight Discrete Logarithms in Composite Groups 5/24 11.00 Uhr
14.8 Olivier Blazy (Hierarchical) Identity-Based Encryption from Affine Message Authentication 5/64 11.00 Uhr
21.8 Frank Quedenfeld An improved fault attack on full round Katan32 5/24 11.00 Uhr
11.9 Daniel Masny Improved Short Lattice Signatures in the Standard Model (L.Ducas, D.Micciancio, CRYPTO'14) 5/24 11.00 Uhr

Polynomial Spaces - A New Framework for Composite-To-Prime-Order Transformations

In this talk we consider the task of transforming constructions from composite order groups with a symmetric pairing to prime order groups. Following the model of Freeman (Eurocrypt2010), this means we need to emulate key properties of such composite-order groups by vectors of elements from prime order groups. Our construction does this by considering vectors of group elements as "polynomials in the exponent". Using our approach, we can gain considerable efficiency improvements compared to previously known solutions. This is join work with Julia Hesse, Carla Rafols, Dennis Hofheinz and Andy Rupp and will appear at CRYPTO2014.

A Generic Algorithm for Small Weight Discrete Logarithms in Composite Groups

Let G be an arbitrary cyclic group of composite order N with G ~ G_1 x G_2. We present a generic algorithm for solving the discrete logarithm problem in G with Hamming weight d*n, d \in (0,1), in time O( p^(1/2) + |G_2|^(H(d)/2) ), where p is the largest prime divisor in G_1 and H() is the binary entropy function. Our algorithm improves on the running time of Silver-Pohlig-Hellman's algorithm whenever d != 1/2. Moreover, it improves on the Meet-in-the-Middle type algorithms of Heiman, Odlyzko and Coppersmith with running time O( |G|^(H(d)/2) ) whenever p < |G|^(H(d)).

(Hierarchical) Identity-Based Encryption from Affine Message Authentication

In this talk, we provide a generic transformation from any affine message authentication code (MAC) to an identity-based encryption (IBE) scheme over pairing groups of prime order. If the MAC satisfies a security notion related to unforgeability against chosen-message attacks and, for example, the k-Linear assumption holds, then the resulting IBE scheme is adaptively secure. Our security reduction is tightness preserving, i.e., if the MAC has a tight security reduction so has the IBE scheme. Furthermore, the transformation also extends to hierarchical identity-based encryption (HIBE). We also show how to construct affine MACs with a tight security reduction to standard assumptions. This, among other things, provides the first tightly secure HIBE in the standard model This is a joint work with Eike Kiltz and Jiaxin Pan, and will appear at Crypto 2014.

An improved fault attack on full round Katan32

In this talk we present an improved fault attack on full round Katan32 which requires less than a minute to execute. Firstly we present a new algebraic model which trivially allows for a key recovery attack on $75$ round Katan32. We extend this model to a fault attack in a realistic fault model and preform a full key recovery using standard notebook computer.

Improved Short Lattice Signatures in the Standard Model

We present a signature scheme provably secure in the standard model (no random oracles) based on the worst-case complexity of approximating the Shortest Vector Problem in ideal lattices within polynomial factors. The distinguishing feature of our scheme is that it achieves short signatures (consisting of a single lattice vector), and relatively short public keys (consisting of O(log n) vectors.) Previous lattice schemes in the standard model with similarly short signatures, due to Boyen (PKC 2010) and Micciancio and Peikert (Eurocrypt 2012), had substantially longer public keys consisting of Ω(n) vectors (even when implemented with ideal lattices). We also present a variant of our scheme that further reduces the public key size to just O(log log n) vectors and allows for a tighter security proof by making the signer stateful.