Paper 2009/136

How to Extract and Expand Randomness: A Summary and Explanation of Existing Results

Yvonne Cliff, Colin Boyd, and Juan Gonzalez Nieto


We examine the use of randomness extraction and expansion in key agreement (KA) protocols to generate uniformly random keys in the standard model. Although existing works provide the basic theorems necessary, they lack details or examples of appropriate cryptographic primitives and/or parameter sizes. This has lead to the large amount of min-entropy needed in the (non-uniform) shared secret being overlooked in proposals and efficiency comparisons of KA protocols. We therefore summarize existing work in the area and examine the security levels achieved with the use of various extractors and expanders for particular parameter sizes. The tables presented herein show that the shared secret needs a min-entropy of at least 292 bits (and even more with more realistic assumptions) to achieve an overall security level of 80 bits using the extractors and expanders we consider. The tables may be used to find the min-entropy required for various security levels and assumptions. We also find that when using the short exponent theorems of Gennaro et al., the short exponents may need to be much longer than they suggested.

Available format(s)
Publication info
Published elsewhere. An abridged version of this paper is to appear in ACNS 2009. This is the full version.
randomness extractionrandomness expansionkey agreementkey exchange protocolspseudorandom function (PRF)universal hash functionleftover hash lemma (LHL)
Contact author(s)
j gonzaleznieto @ qut edu au
2009-03-30: revised
2009-03-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yvonne Cliff and Colin Boyd and Juan Gonzalez Nieto},
      title = {How to Extract and Expand Randomness: A Summary and Explanation of Existing Results},
      howpublished = {Cryptology ePrint Archive, Paper 2009/136},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.