Doing OTP two or more times with a biased TRNG: Will this have the same security as if was done with a non-biased TRNG?

Question

Let's suppose I want to do One-Time-Pad but I only have a biased true random number generator (TRNG).

I XOR to the ciphertext block with another with random data got from the TRNG, e repeat the process two or more times with different random blocks.

Will this scheme make the One-Time-Pad more secure? Will this provide the same security as if was done with a non-biased TRNG?

Answer 1

Better than using it once, but not as good as an unbiased TRNG.

To see this, suppose our TRNG is very biased, producing a zero 10% of the time and an one 90% of the time.

If we use the TRNG twice, for each bit we have four possibilities:

• Both times we get a 0 from the TRNG. This will occur 10% * 10% = 1% of the time.
• The first time we get a 0 and the second time we get a 1: This will occur 10% * 90% = 9% of the time
• The first time we get a 1 and the second time we get a 0: This will occur 90% * 10% = 9% of the time
• Both times we get a 1 from the TRNG. This will occur 90% * 90% = 81% of the time.

So after the XOR, the first and last cases produce a 0, and the second and third cases produce a 1. So 82% of the the time we get a 0 and 18% of the time we get a 1. So the result is still a biased TRNG, but not as bad as the original TRNG. If you repeat this enough times, you could get close enough to 50/50 that it wouldn't matter in practice. A less biased TRNG would get there quicker, but the same principles would apply.

Answer 2

The convergence of your suggested process towards unbiased bits is guided by the Piling Up Lemma. It will be slow. It is more efficient to use unbiasing procedures such as von Neumann unbiasing. See for example this question

But this is of course simpler due to direct XOR.

For $n$ independent identically distributed $\{0,1\}$ valued random variables, $X_1, X_2, \ldots X_n$:

$$ Pr(X_1 \oplus \ldots \oplus X_n = 0) = \frac{1}{2} + 2^{n-1} \prod_{i=1}^n \epsilon_i $$ where $\epsilon_i$ is the bias of $X_i.$ This gives the final bias as

$$ \epsilon_{1,2, \ldots, n} = 2^{n-1} \prod_{i=1}^n \epsilon_i $$

For each bit of your combined blocks, and taking the example of bias $\epsilon_i = 0.4$ for $i=1,\ldots, n$ (corresponding to the 90% in the other answer) we get biases as below

\begin{array}{c|c|c} \textrm{Number of } & \textrm{Resulting Bias} & \textrm{Probability of 1} \\ \textrm{combined blocks ($n$)} & & \\ 2 & 0.32000 & 82.0\% \\ 4 & 0.20480 & 70.4\% \\ 8 & 0.083886 & 58.4\% \\ 16 & 0.014074 & 51.4\% \end{array}

FYI, this slow convergence due to the $2^{n-1}$ factor is the reason linear cryptanalysis works.

Answer 3

Pretty much yes.

Many TRNG designs are based entirely on digital circuitry, and do not involve any analogue components [see note]. It makes them simpler to incorporate on silicon. But unfortunately digital circuitry tends to perform digitally and is therefore quite poor at generating entropy. So rather than giving you a theoretical example, here's a real TRNG with very very poor bias:-

This is from a paper building an FPGA TRNG.

Notice the Decimator. It's role is to successively XOR $K_D$ samples together in order to increase the entropy per output sample. In this case, $K_D=7$, effectively XORing seven OTPs together from your perspective. Later in that paper, $K_D$ reaches 185 for another design. That's 185 biased TRNG samples XORed together using the Piling up lemma. I can't find the reference for you, but I've seen a decimation ratio of 512 in a ring oscillator TRNG.

So you'll find that successive multiple XORing is common in all digital TRNGs in the form of decimation. It avoids more complex entropy extraction techniques such as hashing which require more silicon real estate.

---

Note. I'm positing that in this case purely digital circuitry exists, whilst realising that all circuitry is basically analogue at the micro scale.