弱规则单向函数及其应用

The existence of one-way functions (OWFs) is one of the central results upon which modern cryptography is successfully founded. OWFs can be used to construct pseudorandom number generators (and thereby stream cipher) which can be further used to design pseudorandom functions and pseudorandom permutations (and thereby block cipher). Some OWFs are well structured, for instance, every image has the same number of preimages if the OWF is regular. There are two research lines in constructing cryptographic primitives (e.g., pseudorandom generators, universal one-way hash functions) from one-way functions. One such research is to construct cryptographic primitives from any OWF, and its advantage is that no structure property of the underlying OWF is required in constructing the primitives. Another such of research focuses on more efficient (even nearly practical) constructions of cryptographic primitives from special structured OWFs (e.g., one-way permutation, regular OWF, etc.), and its advantage is that improved (even optimal) parameters can be obtained (e.g., shorter seed length, optimal calls to OWF, etc.). A challenging problem is whether we can construct some efficient (even security-preserving) primitives from a more general class of OWFs. This work introduces a more general class of OWFs called “weakly-regular one-way functions”, and regular OWFs fall into a special case. It shows that in order not to fall into weakly-regular functions, the counterexamples should be somewhat artificial. The approach that bases pseudorandom generators (PRGs) on regular OWFs can be generalized to the more general setting, and concrete PRG from weakly-regular OWFs can be much more seed-length efficient and security-preserving than the HILL-style generators. It is shown that constructing universal one-way hash function (with key length O(nlogn) and output length Θ(n)) from weakly-regular OWF generalizes the state-of-the-art construction that requires an unknown-regular one-way function.