基于格理论的高效伪随机生成器新构造

本文主要探讨了程宽和毕经国在《中国科技论文在线》上发表的一篇关于伪随机生成器（Pseudorandom Generator, PRG）构造的新方案。PRG在密码学领域扮演着关键角色，作为现代加密系统的基础组成部分，其效率和安全性至关重要。 新提出的PRG构造方法创新地利用了格理论中的经典问题，具体是多维子集和问题（Multidimensional Subset Sum, MSS）。作者首先将MSS问题转化为一种单向函数，这种转换利用了MSS问题的困难性，即虽然容易验证给定的子集和是否等于某个目标值，但难以通过已知的和和子集找到原始的元素集合。这种“大致正规”的特性使得MSS单向函数相较于通用单向函数具有更低的种子需求。 在构造过程中，作者采用了单向迭代函数的设计策略，这有助于保持生成的随机序列的不可逆性。通常，对于依赖于一般单向函数的PRG，如果单向函数的输入长度为m，所需的种子长度会达到O(m^7)。然而，由于新方案巧妙地利用了MSS单向函数的特性，种子长度可以显著减少，只需要O(mlogm)，这在实际应用中具有明显的效率优势。 本文的研究不仅提升了伪随机生成器构造的效率，还为密码学研究提供了新的视角，特别是在处理复杂性理论与实际加密实践相结合的问题上。关键词包括计算复杂性理论、伪随机生成器、格问题以及单向函数，这些都反映出作者对基础理论的深入理解和在实际应用中的创新思维。该成果对于提高密码系统的安全性和性能，尤其是在资源受限的环境中，具有重要的理论价值和实用意义。