4
$\begingroup$

I am using a linear feedback shift register (LFSR) in a scrambler configuration as a randomness extractor for a weakly random source. This source is semi-random (aka. Santha-Vazirani source): the bits are correlated and biased (with a min-entropy of ~0.5 per bit). Here is an example of a LFSR in a scrambler configuration (this one is 12-bit while I am using a 32-bit register) with a downsampler:

LFSR scrambler

The weakly random entropy source feeds the LFSR scrambler directly and the output is highly downsampled (one output bit is taken for every e.g. 1000 weak bits). This method has been proposed here. However, I did not find examples where LFSR scramblers are used as randomness extractors. Hence, I have the following questions:

  1. Is using a scrambler for randomness extraction of semi-random data a valid use? How does it compare to other extractors? For example, a von Neumann extractor is only suitable for biased, independant (not correlated) input and is linear time.
  2. How to compute how much downsampling/decimation is required at the output of the LSFR so that the output is suitable for cryptographic use (given an estimation of the input min-entropy)?
  3. What implications does taking the whole register at once (e.g. output 32 bits every 32000 weak input) rather than 1 bit every 1000 input have?

context: The LFSR is used in the following TRNG:

TRNG

Improve this question
$\endgroup$
7
  • $\begingroup$ What are you sampling? $\endgroup$
    – Paul Uszak
    Jul 11, 2021 at 20:26
  • $\begingroup$ @PaulUszak XORed output from multiple ring oscillators. $\endgroup$
    – DurandA
    Jul 11, 2021 at 23:28
  • 1
    $\begingroup$ Not familiar with hardware part, what is the weakness of ring oscillators? Dependence of consequent samples or bias away from 50%? $\endgroup$
    – Fractalice
    Jul 14, 2021 at 9:38
  • $\begingroup$ @Fractalice The sampled signal from the oscillators has both strong periodicity and bias characteristics. You can see both in these noise images I generated. In the 4x3-stages image, we can distinguish some line patterns which is a direct consequence of the periodicity/the lack of jitter. Compared to true random data, the oscillators produce more white pixels which means a bias towards 1. $\endgroup$
    – DurandA
    Jul 16, 2021 at 4:59
  • $\begingroup$ @DurandA You can't do that. The eye can't distinguish between autocorrelation (R) of $R \leqslant 10^{-3}$ and $R > 10^{-3}$. These are commonly accepted correlation limits. $\endgroup$
    – Paul Uszak
    Aug 19, 2021 at 22:54

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.