The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Cryptographic Extraction

Krawczyk, H (IBM Research, USA)
Wednesday 01 February 2012, 09:00-09:45

Seminar Room 1, Newton Institute


Randomness extractors are algorithms that map sources of sufficient min-entropy to outputs that are statistically close to uniform. Randomness extraction has become a central and ubiquitous notion in complexity theory and theoretical computer science with innumerable applications and surprising and unifying connections to other notions. Cryptography, too, has greatly benefited from this notion. Cryptographic applications of randomness extractors range from the construction of pseudorandom generators from one-way functions to the design of cryptographic functionality from noisy and weak sources (including applications to quantum cryptography) to the more recent advances in areas such as leakage- and exposure-resilient cryptography, circular encryption, fully homomorphic encryption, etc. Randomness extractors have also found important cryptographic uses in practical applications, particularly for the construction of key derivation functions. In many of these applications, the defining property of randomness extractors, namely, statistical closeness of their output to a uniform distribution, can be relaxed and replaced with computational indistinguishability. Extractors that provide this form of relaxed guarantee are called 'computational extractors'. In this talk I will cover some recent advances in the understanding and applicability of computational extractors with particular focus on their role in building key derivation functions. As a connection between this talk and the question 'Is Cryptographic Theory Practically Relevant?' see


[pdf ] [ppt ]


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧