Add first TCC review

1 files changed, 246 insertions, 0 deletions

diff --git a/tcc-2019-232.txt b/tcc-2019-232.txt
new file mode 100644
index 0000000..e5c3643
--- /dev/null
+++ b/tcc-2019-232.txt
@@ -0,0 +1,246 @@
+Overall grade: 5
+Confidence level: 3
+Technical: 3
+Editorial: 1
+
+Summary of the paper
+--------------------
+
+This paper considers the problem of building pseudorandom functions (PRF) from
+non-adaptive pseudorandom functions (naPRF). The main result rules out the
+existence of a fairly general class of one-call fully black box constructions
+(in the sense of [RTV04]). Specifically, the authors consider constructions
+with the following structure:
+
+1. a (possibly seeded) preprocessing function is applied to the input
+
+2. the preprocessed input is fed to the naPRF, importantly (and this
+   is the only real restriction compared to arbitrary one-call constructions)
+   the seed used in computing the naPRF is a uniform random variable
+   independent of the input, i.e. it is what the naPRF "expects" as a seed
+
+3. a (possibly seeded) post-processing function is applied to the output of the
+   naPRF
+
+The proof of the main result uses the standard fact that fully black-bock
+constructions relativize: for a one-call construction F of the type described
+above, the authors construct an oracle relative to which a naPRF exist but for
+which F is not secure against adaptive adversaries. This oracle is similar to
+the oracle constructed in (Myers 2004) and can be informally described as
+follows:
+
+1. the first part of the oracle is a uniformly random (seeded) oracle O, which
+   in particular is an exponentially strong PRF
+
+2. the second part of the oracle, R, acts as an "inverter" for F, but *only* to
+   an adversary which is able to prove that it is making adaptive queries to F
+
+The authors then proceed to prove that relative to (O, R):
+
+1. O is a naPRF. This is the most challenging part and requires showing that
+   a non-adaptive adversary cannot take advantage of R. This is achieved by
+   showing how, to a non-adaptive adversary, R can be (approximately) simulated
+   efficiently.
+
+2. F instantiated with O is not a PRF. This part is fairly straightforward
+   since R was designed specifically to break F^O.
+
+The above proof is only valid when the preprocessing function satisfies
+a "universality" property. In the last part of the paper, the authors show how
+this restriction can be removed in specific cases.
+
+Strengths
+---------
+
+* The question of building PRFs from naPRFs is important and this paper nicely
+  complements a small set of results ruling out natural classes of
+  constructions.  In particular it shows that the one-call construction of
+  (Berman, Haitner 2015) cannot be proved secure in a black-box manner when the
+  naPRF is only secure to PPT adversaries.
+
+* The class of one-call construction which is introduced in this paper is
+  interesting. In particular, the authors convincingly show that a subtle
+  interplay between the pre-processing and post-processing functions requires
+  both a careful analysis and additional assumptions (like c-universality).
+
+Weaknesses
+----------
+
+* Simply ruling out one-call constructions is arguably restricted. The authors
+  make a convincing case that this is already non-trivial and progress compared
+  to what is already known. However, it could have been nice to explain in
+  greater detail the main challenges in extending this result to arbitrary
+  constant number of calls.
+
+* The paper seem to have been put together rather hastily and would benefit
+  from a thorough proofreading pass (more on this below).
+
+Technical inaccuracy
+--------------------
+
+1. Although I am quite confident that the results and proof is correct, it seems
+that there is an inaccuracy in the proof:
+
+* it starts in Definition 5, p. 13 where the definition of the good seeds
+  requires |C(s, X_1)| > l/(c-1) (and similarly for X_2 and X). This is
+  inconsistent with the informal description given above the definition which
+  requires that there is no c-way collision in C(s, X_1). Note that the absence
+  of a c-way collision implies |C(s, X_1) > l/c-1) but the converse it not
+  true. 
+
+* the previous point becomes problematic in appendix E.2 (proof of Lemma 12),
+  where it is claimed that |C(s, T_1)|> l/(c-1) implies that when considering
+  a subset I of l/2 indices, there must be at least l/2(c-1) distinct values in
+  |C(s, T_1[I])|. This is not true, since C(s, T_1) could for example comprise:
+
+  * l/(c-1) distinct values in the first l/(c-1) indices
+  * the same value repeated in the next l - l/(c-1) indices
+
+  Clearly, the set containing the last l/2 indices will not have the desired
+  property (for, say, c greater than 4)
+
+For this reason, I believe that Definition 5 should be fixed to reflect the
+original intended meaning (absence of c-way collision). Then, the entire proof
+should go through after replacing all the instances (not just in appendix E.2)
+of the clause "|C(s, X)|> l/(c-1)" by the clause "there is no c-way collision
+in C(S, X)". And only using that "|C(s, X)| > l/(c-1)" when necessary as
+a property implied by the absence of a c-way collision. 
+
+In particular, Definition 12 (Badf) and the Proof of Lemma 15 (p. 34) needs to
+be fixed in a similar manner.
+
+Comments on the presentation
+----------------------------
+
+Although the general structure is good, the paper suffers at times from
+inconsistencies and redundancies which interfere with the flow of the paper:
+
+* the security parameter is called lambda in the introduction, but then it
+  seems that n plays the role of lambda (or is it n+sigma?)
+
+* the class of one-call constructions considered in the paper is described
+  three times, which is at least one too many. I suggest the one at the
+  beginning of section 2.1 be removed.
+
+* beta-sparse and beta-good are used quite inconsistently. In particular, in
+  section 2.2, an informal description of a beta-good seed is given, but the
+  description given turns out to correspond to what is later defined as
+  beta-sparse. However, section 2.2 does require the notion of beta-good to be
+  correct.
+
+* the choice of name 1/2-good for elements in the co-domain of G is
+  questionable since it could be confused with the notion of a beta-good seed.
+
+* the formalism of function families in section 3 is unnecessarily complicated:
+
+  - splitting F into two functions F.Kg and F.Eval is unnecessary since in all
+	cases considered in the paper the key distribution is uniformly random.
+	I recommend having only F taking as input a uniformly random key. In fact,
+	this is how it is done in most places in the proof, and the function F.Kg
+	is not used consistently.
+
+  - the functions do not need to take 1^n as an extra input since it can be
+	inferred from the key length. In fact, this input is already dropped in
+	most places, so I would recommend not introducing it at all.
+
+* the notation H^O for the naPRF in the relativized world seems unnecessary
+  since it is just a different name for O
+
+* the overview in Section 2.2 is quite confusing and only became clear after
+  reading the formal proof:
+
+  - throughout it says that the oracle R provides requests or challenges. This
+	is counterintuitive since we usually think of an oracle as something which
+	is queried, not the converse. It could make sense to, already at this
+	stage, describe the "three-part" structure of the oracle, whose first two
+	parts effectively can be thought of as providing challenges.
+
+  - introducing the three-part structure would also be a good way to explain
+	that the oracle is designed to force the adversary to make adaptive queries
+	by committing to a value y before receiving the input to the next query. At
+	the moment this point is a bit lost in the overview and only described by
+	the somewhat cryptic "R issues x_{i+1} only after learning y_i".
+
+* the flow of the proof is a bit hard to follow since it is split in many
+  lemmas with many forward pointers. I wonder whether some re-ordering could
+  make it easier to follow.
+  
+* the proof could also be factored better: I believe the goal of Lemma 4 is to
+  factor out parts of the proof, but it does not quite achieve this goal. For
+  example the proof of Lemma 12 is extremely similar to the proof of Lemma
+  4 but does not use it. Also, whenever Lemma 4 is invoked, the preliminary
+  work to invoke it is identical, so I suspect that even more could be factored
+  out with a slightly more general lemma.
+
+* The quantity 2l/4c which appears frequently should be simplified to l/2c.
+
+* Lemma 11: I believe the factor q is unnecessary since there is at most one
+  query where X_2 is sampled. So instead of a union bound, it seems that one
+  could the disjoint events "X_2 is sampled at query i" for i in {1, ..., q}.
+
+Typos and minor inaccuracies
+----------------------------
+
+The following list is far from being exhaustive:
+
+* Section 1, paragraph "The BH approach", single-line equation: k should be
+  replaced by s
+
+* Section 1, paragraph "Our results in detail": "which often requires the input
+  to H to (be) fresh" (missing word)
+
+* Section 2.2, paragraph "Security of H revisited": "considering only
+  beta-goods" --> "considering only beta-good seeds"
+
+* Section 2.2, paragraph "Security of H revisited", last sentence:
+  "beta-sparse" --> "beta-good" (see also above comment on inconsistent use of
+  beta-sparse/good)
+
+* Section 4.2, last paragraph: "closely to related to" --> "closely related to"
+  (extra "to")
+
+* Section 4.2, last paragraph: "the challenge in the" --> "the challenge"
+
+* Section 4.3, first paragraph: "Putting Propositions 1 and 2 (together)"
+  (missing word)
+
+* Section 5.4, first paragraph: "The challenge is (to)" (missing word)
+
+* Appendix D: the set Q^* which is used throughout has not been formally
+  defined. In particular, Fig. 4 should show how it is computed.
+
+* Proof of Lemma 11: beta-good should be replaced by beta-sparse throughout
+
+* Proof of Lemma 11: both products should be indexed starting from i=0
+
+* "Proof overview" of Lemma 14: "of size at least l(k+1)/2c(c-1)", the k should
+  be replaced by c
+
+* "Proof overview" of Lemma 15, last single-line equation: there is a missing
+  2.sigma multiplicative factor in front of the last summand
+
+* Appendix E.2: "it must be that there are at least l/2(k-1)", the k should be
+  replaced by c
+
+* Appendix E.2: "of the Z_1[i]'s (Let Z_1[i])" some extra words should be
+  removed
+
+* Appendix E.2: "where t = |J_s| \geq l/2c - l/2(c-1)" it should be "l/2(c-1)
+  - l/2c"
+
+* Proof of Lemma 14, last line: t= l(c+1)/2c(c-1) (there is a missing (c+1)
+  factor)
+
+* Proof of Lemma 15: what is proved is an upper bound  on Pr[Bad_2 and
+  j < t | not Bad] (and similarly for j > t + p -1). In other words, the
+  condition on j should be put on the left-hand side of the conditioning.
+
+* Appendix G, equation (17): l^* and delta do not exist in this context.
+  delta*l^* should be replaced by l/c
+
+Summary of recommendation
+-------------------------
+
+The problem and the results are interesting. I believe this paper will be
+a valuable contribution to TCC if the above comments are addressed and after
+a thorough pass of proofreading.