Random Numbers from Hard Problems: LWE Toy RNG

Summary

From the above definition of PRNG, we know that the goal of an RNG is to generate an output that is indistinguishable from truly random. The Decision LWE (DLWE) problem has exactly this property.This is the famous LWE equation\[ b_i = a_i \cdot s + e_i \pmod q \]Where$s$ (secret vector)A secret vector (the key) that no one knows.$a_i$ (public vector)A public vector of random numbers.$e_i$ (small noise)A small error value (+1 / 0 / -1) to smudge the result$q$ (prime modulus)A large prime number modulus$b_i$ (output)The final result, which is publicly knownThe DLWE assumption states that the output $b_i$ of the LWE problem is computationally indistinguishable from a uniform random number in $\mathbb{Z}_q$.In other words, when $s$ and $e_i$ are secret and only $a_i$ and $q$ are known publicly, the output $b_i$ is computationally indistinguishable from a random number between 0 and q-1.Unfortunately, the LWE assumption requires use to get $a_i$ from a random uniform distribution for each sample. Since a PRNG must be entirely deterministic and reproducible from its seed, we cannot generate a truly random $a_i$​ at each step, so we need to deviate from the LWE problem a bit.