Add TCC 2021 review

1 files changed, 105 insertions, 0 deletions

diff --git a/tcc-2021-154.txt b/tcc-2021-154.txt
new file mode 100644
index 0000000..e77a2b8
--- /dev/null
+++ b/tcc-2021-154.txt
@@ -0,0 +1,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.