5
$\begingroup$

Let $ext$ be a single-source randomness extractor which takes a $d$-bit seed and a $n$-bit source as input and produces a $m$-bit output. Suppose we have a source $X$ with min-entropy $k$. Is it possible to reuse $X$ with different random seeds $S_1, . . . S_l$ for $l ≥ 2k$? In other words: Is $(S1, . . . S_l, ext(S_1, X), . . . , ext(S_l, X))$ statistically close to $(U_{l(d+m)})$?

As a hint I was told to think of ext being the inner product over bits.

I know the answer is no, this is not secure, but why? Especially in the case of $ext$ being the inner product over bits.

$\endgroup$
  • $\begingroup$ In this case $ext(S_i,\cdot)$ is a linear function of the bits of its input $X$. With enough of them you are bound to have some be linearly dependent, which leads to clear correlations/artifacts in the output. $\endgroup$ – Mikero Nov 29 '15 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.