基于单向函数的伪随机产生器与通用单向哈希函数

One-way function based pseudorandom generator and universal one-way hash function

重点回顾基于单向函数的伪随机产生器,以及通用单向哈希函数的研究现状,介绍相关研究的最新进展,并对通用单向哈希函数设计方法给出系统性阐述。单向函数蕴涵伪随机产生器是密码学中的基础问题,是现代密码学的基础。单向函数可以用来构造伪随机产生器进而构成流密码算法,或是在伪随机产生器的基础上进一步构造伪随机函数和伪随机置换从而用作分组加密算法。随机迭代技术被提出并经精练后,可用于基于规则单向函数的伪随机产生器设计。单向函数蕴涵通用单向哈希函数是现代密码学最核心的基础理论之一。关于通用单向哈希函数可以基于任意单向函数构造而来。通用单向哈希函数的应用包括基于最小假设的数字签名、Cramer-Shoup加密体制、统计隐藏承诺体制等。

A survey is given to revisit the problem of basing pseudorandom generators on one-way functions,and the state of the art on universal one-way hash functions from one-way functions is reviewd.That one-way functions（OWFs）imply pseudorandom generators（PRGs）is one of the central results upon which modern cryptography is successfully founded. ＂The randomized iterate＂technique is originally used and refined in constructing PRGs from regular OWFs.The seminal result that one-way functions（OWF）imply universal one-way hash functions（UOWHFs）constitutes one of the central pieces of modern cryptography.The principle possibility result is that UOWHFs can be based on any OWF.Applications of UOWHFs include basing digital signatures on minimal assumptions（one-way functions）,Cramer-Shoup encryption scheme,statistically hiding commitment scheme,etc.