Random Numbers from Hard Problems: LWE Toy RNG
7 months ago
- #Cryptography
- #LWE Problem
- #Random Number Generation
- The Blum-Micali algorithm is a simple and elegant method for constructing a Cryptographically Secure Pseudo-Random Number Generator (CSPRNG) based on the discrete logarithm problem.
- A toy RNG is presented, inspired by Blum-Micali but based on the Learning with Errors (LWE) problem, emphasizing simplicity and elegance.
- The Decision LWE (DLWE) problem ensures that the output is computationally indistinguishable from true randomness, a key property for PRNGs.
- The algorithm requires initial parameters: a prime modulus (q), a seed vector (a₀), a generator matrix (G), small noise (e₀), and a secret seed vector (s).
- The generation loop involves four steps: creating an LWE sample, extracting an output bit, updating the internal state via confusion and diffusion, and updating the error term.
- An example run demonstrates the algorithm's operation, showing how bits are generated and the state evolves over iterations.
- The blog emphasizes that this is a toy RNG for educational purposes, not for real-world security applications, and invites analysis and critique.