1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
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.
|
