Implementing randomness extractors

Question

A randomness extractor is a function that takes an input sampled from high entropy distribution and outputs a value that is close to uniform distribution. It is slightly different from a PRG. PRGs take an input sampled from uniform distribution and output a larger length string which is computationally indistinguishable from uniform. Whereas randomness extractors take an input sample from high entropy distribution and output a smaller length string statistically close to uniform distribution.

In my scheme, I use randomness extractors. In the scheme, the extractor takes an element uniformly sampled from a subgroup of $Z_N^*$, where $N$ is a product of 2 large primes. The extractor needs to output a bit string. I want to implement the scheme but couldn't find any implementations of randomness extractors. Are there any randomness extractors in sagemath, or any other library?

Answer 1

Whereas randomness extractors take an input sample from high entropy distribution and output a smaller length string statistically close to uniform distribution.

Not quite. A randomness extractor is not simply a function $F\colon A \to S$ such that $F(X)$ has small distance from uniform if $X$ has high min-entropy. Rather, a randomness extractor is a keyed family of functions $F_k\colon A \to S$ such that if $K$ is uniformly distributed and $X$ has high min-entropy, then $F_K(X)$ has small distance from uniform. In other words, the premise is that you already have a uniform random key.

So, there is essentially no reason to use a randomness extractor in a practical application. Generally, either:

1. You have a secret with high enough min-entropy to do cryptography.
   • Great! Use HKDF-SHA256 or your favorite KDF to derive keys from it for each cryptosystem you want to use.
2. You don't have a secret with high enough min-entropy to do cryptography.
   • No amount of cryptidigitation with randomness extractors will raise its min-entropy. Just flip the coin a few more times.

Randomness extractors are essentially of theoretical interest only, so it is not surprising if you have trouble finding practical implementations of them labeled as such (although any universal hash serves as a randomness extractor with the leftover hash lemma). If you actually want to do cryptography, just feed your initial secret with high min-entropy through a hash function like HKDF-SHA256 or SHAKE128.

Answer 2

There are weird and wonderful theoretic extractors in the literature, but in practice people end up using some form of generic hash algorithm. You either write your own or use a recognised form. The implementation language can be anything that can do the following:-

1. Writing your own usually comprises some form of vector multiplication. So either a Toeplitz matrix, or just a rectangular matrix of random bits/integers. You then apply the modulus depending on whether you're trying to output bits or octets. So using matrix $M$ on an input entropy vector $x$ gives $\operatorname{Ext}(x) = M \cdot x \mod n$, where $n$ would be the modulus, say 2, $2^8$ or a prime in some cases. The ID Quantique random number generators use the random bit wise mod 2 method.

2. The standard forms can be either cryptographic or non cryptographic hashes. SHA*, HMAC, CRC*, Pearson, etc. The USB format OneRNG uses CRC16 and I'm partial to Pearson.

It doesn't really matter as the typical application of a randomness extractor means that the overall system state is not recoverable.

Although... You mention extracting from a sub group of $Z_N^*$. It is unusual to extract from an algorithm, as what you will have is a pseudo random generator. If this is really the case, a cryptographic hash would be needed as state discovery would be mathematically possible. Forwards and backwards security would be compromised otherwise. However, I've never seen a formal randomness extractor and an algorithmic state mutator together in one construction.

An alternative is to stick with von Neumann (vN) if inversion is not possible due to some algebraic property of $Z$. You then have to decorrelate $x$, create independent samples and only then apply vN. The most common decorrelation method is dropping higher bits from $x$ until autocorrelation levels become acceptable. Only you know your $Z$'s behaviour, so lower bits may have to be dropped instead. There is also FIR filtering across sequential $x_i$ values. XOR of sequential $x_i$ values can also act as an ersatz FIR filter. If inversion is possible, simple vN will still be insecure for cryptography though.