Overall grade: 5 Confidence level: 3 Editorial: 2 Summary ======= This paper considers the problem of building pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs) from regular one-way functions (OWFs), when the regularity is unknown. Black-box constructions for this specific case are already known, using O(n) calls to the OWF and seed/key length O(n), which is optimal up to logarithmic factors. However these known constructions make adaptive calls to the one-way function (typically, the one-way function is applied to the hashed output of the previous call). The main contribution of the present work is to give two new constructions (of PRG and UOWHF respectively) which only make non-adaptive calls to the one-way function, and thus can be implemented more efficiently when calls can be made in parallel. The two constructions are simple and look almost identical: the common structure is to uniformly sample t independent inputs x_1, ... , x_t and a 2-universal hash function h (which needs to be shrinking for the UOWHF construction) and output the concatenation of the h(x_i, f(x_{i+1})) for i in [1 .. t-1]. For the UOWHF construction, f(x_1) and x_t need to be part of the output as well. The two constructions are proved to be secure (via black-box reductions) for t = O(n/log n) and thus achieve an optimal call complexity, but at the cost of a suboptimal key/seed length of O(n^2). General comments ================ The problem considered in this paper is natural and interesting, since the role/importance of adaptivity in many cryptographic constructions and reductions is still poorly understood. The results are compelling: it is satisfying that simple and similar constructions yield secure constructions, and the proofs are relatively simple to follow. I checked the proof fairly carefully and everything seems correct (see one minor technical comment below). The main open question suggested by this work is whether the increase in key/seed length (from O(n) to O(n^2)) is inherent to non-adaptivity or could be avoided with better constructions. Intuitively, it seems necessary but the authors do not prove any result in this direction. However, tighter lower bounds for non-adaptive constructions seem hard to obtain. Technical comments ================== * in the proof of claim 3.3 at the bottom of page 13, it is stated that "given f(x_1), the min-entropy of x_1, f(x_2) is at least n-2.beta.log n". This uses some notion of conditional min-entropy which hasn't been defined by the authors. Since there are several ways to define conditional min-entropy, a formal definition should be given in the preliminaries. Relatedly, the end of this proof uses the leftover hash lemma but the version stated in the preliminaries is for (standard) min-entropy. So an appropriate version of the leftover hash lemma needs for conditional min-entropy (with auxiliary variable) needs to be stated in the preliminaries. I didn't check carefully, but it seems that everything should still go through with average conditional min-entropy. * this is more of a point about exposition, but I couldn't figure out why it is important to output x_t as the last block of the UOWHF construction. Where does it matter in the proof? I might have missed something, but a little bit more explanation about it would be nice. Minor comments ============== The paper contains many typos and would benefit from a thorough proofreading pass. A non exhaustive list: * abstract, last sentence of first paragraph: black-cox --> black-box * bottom of page 2: extra comma and space after O(n^7) * page 3, "Lower bounds": G:{0,1}^m --> {0,1}^{m+s}, I think the m should be replaced with n * page 6, "Regular one-way functions": consecrated --> concentrated * page 9, above Definition 2.8: refinement --> relaxation * page 9, above Lemma 2.9: collision resistance --> collision resistant * page 10, beginning of Lemma 2.16: some sets --> some set * page 11, Lemma 3.2: the leftmost probability should also be over the sampling of h * page 11, Algorithm 1, item 2: last superscript should be (t-l+1)n log n (there is +1 missing) * page 12 equation 1: leftmost probability is also missing the sampling of h * page 12, claim 3.3 above equation (2): "and a function" --> "and every function" (otherwise it is unclear that it is a universal quantification over i) * page 16, first line of Proof of Claim 4.4: Sine --> Since * page 16, first line of Proof of Claim 4.4: hols --> holds * page 19, last line of proof of Claim 4.6: last --> penultimate * page 19, equation of Claim 4.7: the summation should be over x_1' in f^{-1}(f(x_1)) (there is a missing 1 subscript) * page 20, equation (10): same as previous item * page 21: same as previous item * page 21: "equality holds bt" --> "equality holds by" Summary ======= I believe this paper will be a valuable contribution to the TCC community after the above remarks are taken into account.