Random Numbers from Hard Problems: LWE Toy RNG
7 months ago
- #Cryptography
- #LWE Problem
- #Random Number Generation
- Blum-Micali算法是一种基于离散对数问题构建密码学安全伪随机数生成器(CSPRNG)的简洁优雅方法
- 本文展示了一个受Blum-Micali启发、基于容错学习(LWE)问题的玩具级随机数生成器，着重突出其简洁性与优雅性
- 决策型LWE(DLWE)问题确保算法输出在计算上与真实随机数不可区分，这是PRNG的核心特性
- 算法初始化需要五个参数：素数模数(q)、种子向量(a₀)、生成矩阵(G)、小误差项(e₀)和秘密种子向量(s)
- 生成循环包含四个步骤：创建LWE样本、提取输出位、通过混淆与扩散更新内部状态、更新误差项
- 示例运行演示了算法工作流程，展示比特生成过程及状态在迭代中的演变
- 博客强调这仅是教育用途的玩具级RNG，不适用于实际安全场景，并欢迎分析指正