Random Numbers from Hard Problems: LWE Toy RNG

We use the LWE equation to combine our current secret state $s_i$ with the public vector a and the current error $e_i$. This gives us a value $b_i$ that is indistinguishable from random.

\[ b_i = a \cdot s_i + e_i \pmod q \]

Just like Blum-Micali uses a hard-core predicate, we extract a single bit from $b_i$ that is provably hard to guess. For LWE, we can use the MSB for this purpose.

\[ \text{output\_bit}_i = \lfloor \frac{2 \cdot b_i}{q} \rfloor \]

This gives us a 0 if $b_i$ is in the lower half of \(\mathbb{Z}_q\) and a 1 if it's in the upper half.

Now, we want to update the secret state so that we can generate the next pseudorandom bit. We will incorporate Shannon's Confusion and Diffusion to thwart statistical attacks that can predict the next state from the previous state(s).

Here we use a two-step process that provides diffusion and confusion:

1. Linear Mix (Diffusion): We multiply the current state by our generator matrix G. This mixes all the components of the secret vector together. \[ s'_i = G \cdot s_i \pmod q \]
2. Non-linear Transform (Confusion): Here, we square each element of the mixed vector (Hadamard Product). This breaks the predictable linearity. \[ s_{i+1} = s'_i \odot s'_i \pmod q \]

Finally, we need a new error term for the next iteration. To prevent the output bit from leaking information about the next error, we derive it from the low-order bits of $b_i$, which are statistically independent from the MSB we just outputted.

\[ e_{i+1} = (b_i \pmod 3) - 1 \]

This gives us a pseudorandom choice of -1, 0, or +1 for the next round.

By repeating these steps, we can generate a long sequence of pseudorandom bits from a single initial secret seed, $s_0$.

\[ b_0 = a \cdot s_0 + e \pmod q \] \[ b_0 = (2 \cdot 9 + 8 \cdot 5 + 10 \cdot 4 + 1 \cdot 1) + 1 \pmod{17} \] \[ 99 + 1 \pmod{17} \implies 100 \pmod{17} \]

Therefore \[ b_0 = 15 \]

\[ output\_bit_0 = \lfloor \frac{2 \cdot 15}{17} \rfloor = \lfloor \frac{30}{17} \rfloor = 1 \] The first output bit is 1.

First, the linear mix (diffusion) with the new matrix: \[ s'_0 = G \cdot s_0 = \begin{pmatrix} 2 & 3 & 3 & 8 \\ 9 & 7 & 10 & 6 \\ 0 & 12 & 8 & 8 \\ 9 & 13 & 0 & 10 \end{pmatrix} \begin{pmatrix} 9 \\ 5 \\ 4 \\ 1 \end{pmatrix} = \begin{pmatrix} 53 \\ 162 \\ 100 \\ 156 \end{pmatrix} \pmod{17} = \begin{pmatrix} 2 \\ 9 \\ 15 \\ 3 \end{pmatrix} \] Next, the non-linear transform (confusion): \[ s_1 = s'_0 \odot s'_0 = [2^2, 9^2, 15^2, 3^2] \pmod{17} \] \[ [4, 81, 225, 9] \pmod{17} \] Our new secret state is $s_1$ = [4, 13, 4, 9].

\[ e_1 = (b_0 \pmod 3) - 1 = (15 \pmod 3) - 1 = 0 - 1 = -1 \] The next error is $e_1$ = -1.

\[ b_1 = a \cdot s_1 + e_1 \pmod q \] \[ b_1 = (2 \cdot 4 + 8 \cdot 13 + 10 \cdot 4 + 1 \cdot 9) - 1 \pmod{17} \] \[ 161 - 1 \pmod{17} \implies 160 \pmod{17} \] Our result is $b_1$ = 7.

\[ \lfloor \frac{2 \cdot 7}{17} \rfloor = \lfloor \frac{14}{17} \rfloor = 0 \] The second output bit is 0.

\[ s'_1 = G \cdot s_1 = \begin{pmatrix} 2 & 3 & 3 & 8 \\ 9 & 7 & 10 & 6 \\ 0 & 12 & 8 & 8 \\ 9 & 13 & 0 & 10 \end{pmatrix} \begin{pmatrix} 4 \\ 13 \\ 4 \\ 9 \end{pmatrix} = \begin{pmatrix} 131 \\ 221 \\ 260 \\ 295 \end{pmatrix} \pmod{17} = \begin{pmatrix} 12 \\ 0 \\ 5 \\ 6 \end{pmatrix} \] \[ s_2 = s'_1 \odot s'_1 = [12^2, 0^2, 5^2, 6^2] \pmod{17} \] \[ [144, 0, 25, 36] \pmod{17} \] Our new secret state is $s_2$ = [8, 0, 8, 2].

\[ e_2 = (b_1 \pmod 3) - 1 = (7 \pmod 3) - 1 = 1 - 1 = 0 \] The next error is $e_2$ = 0.