[Cryptography] Pure Randomness Extracted from Two Poor Sources

[dj at deadhat.com]

On 12/24/16 4:39 PM, Ron Garret wrote:
> http://cacm.acm.org/magazines/2017/1/211100-pure-randomness-extracted-from-two-poor-sources/fulltext
>
>

This is another paper with the HECS (Hidden Explicit Construction
Syndrome). If I have managed to understand it correctly, it is showing a
lower bound on the distance from uniform of the 2Ext algorithm. There's
another paper ( https://arxiv.org/abs/1005.051 ) that points out that 2Ext
is safe against quantum entangled adversaries, which is nice. Lets all use
2Ext.

My problem is with 2Ext ( https://www.cs.nyu.edu/~dodis/ps/2-ext.pdf -
another paper with HECS).
It is defines a blender(X,Y) and invokes a Trevisan seeded extractor
trevisan(S,Y). (Trevisan extractors are based on error correcting codes).
You use the blender to make the seed for the Trevisan seeded extractor.
I.E. 2Ext(X,Y) = trevisan(blender(X,Y),Y).

The blender algorithm defines a series of square, full rank matrices, one
matrix for each output bit. The matrix elements are bits. The sides are
length |X| and |X|=|Y|.
The algorithm is output_bit_x = matrix_x * X (as a column matrix) inner
product multiply with Y.

The matrix construction is in the paper and leads to a fairly sparse
matrix, which is nice for implementation.

The problem I have is when you try it, the blender output is substantially
more biased than the inputs, even with uniform inputs and when I try it
with randomly generated full rank matrices, I get a much better result. So
the min entropy of the seed is reduced relative to just trevisan(X,Y) and
the random matrices (which the paper affords worse bounds) gets a better
result in practice. This doesn't seem right to me.  I'd like to use 2Ext,
but until these loose ends are understood, it's a no go.

Note the title of the journalist article you link is misleading. The
paper's claims are properly worded and they don't claim to produce 'Pure
Randomness'.

DJ