Seminars at the Faculty of Informatics

The Faculty of Informatics is pleased to announce a seminar given by Dr. Martijn Stam


TITLE: A New Randomness Extraction Paradigm for Hybrid Encryption

SPEAKER: Dr. Martijn Stam, EPFL, group LACAL (Laboratory for Cryptologic Algorithms)

DATE: Tuesday, October 7th, 2008

PLACE: USI Università della Svizzera italiana, room SI-008, Informatics building (Via G. Buffi 13)

TIME: 15.30



In the design of public key cryptosystems, it is customary to use a hybrid approach. A very fast symmetric cryptosystem (such as AES) is used to encrypt the data (or message) under a session key. This session key is freshly generated and encapsulated using a true public key primitive (called key encapsulation). Several results are known that relate the security of the whole system to that of its components. We refine one of these approaches and show how weak key encapsulation can be turned into strong key encapsulation based on randomness extraction.

More technically, our approach provides an efficient generic transformation from 1-universal to 2-universal hash proof systems.

The transformation involves a randomness extractor based on a 4-wise independent hash function as the key derivation function.


In this talk, we will explain our result (and the related theory of secure hybrid encryption) on the hand of the most interesting example based on groups where finding discrete logarithms is hard. In particular, we will show that a hybrid version of 1991's Damgaard's ElGamal public-key encryption scheme is secure under the decisional Diffie-Hellman (DDH) assumption.


This is joint work with Eike Kiltz, Krzysztof Pietrzak and Moti Yung.

Paper available through



Martijn Stam obtained his MSc (1999) and PhD (2003) at the Technische Universiteit Eindhoven, the Netherlands. Afterwards he spent time as a postdoc at the University of Bristol (UK); since 2006 he is a postdoc at EPFL in the group LACAL (Laboratory for Cryptologic

Algorithms) of prof.dr. Arjen Lenstra.


HOST: Prof. Thomas Shrimpton

URL 1: