Add TCC20 review

1 files changed, 135 insertions, 0 deletions

diff --git a/tcc-2020-153.txt b/tcc-2020-153.txt
new file mode 100644
index 0000000..5003c5a
--- /dev/null
+++ b/tcc-2020-153.txt
@@ -0,0 +1,135 @@
+Grades
+------
+
+Overall grade: 5, Solid submission, should be accepted
+Confidence level: 3, Confident (I know the area and I studied the paper in sufficient detail)
+Editorial: 2, Could use some improvement
+Suitability: 3, Fits the conference
+
+Summary
+-------
+
+This paper is concerned with the backdoored random oracle (BRO) model [BFM18]
+in which adversaries, in addition to having query access to a random oracle,
+can compute arbitrary functions (backdoors) of the random oracle.  While
+a single BRO cannot possess any meaningful security, a natural question is
+whether several BROs can be combined to produce a new object with meaningful
+security guarantees. This question was partially answered for specific security
+guarantees (e.g. PRG, one-wayness) in [BFM18]. In this paper, the authors
+consider the question in the indifferentiability framework [MRH04]. 
+
+The main contributions are:
+
+* an indifferentiability analysis of two combiner constructions: the xor
+  combiner for the 2-BRO model and a combiner based on 2-out-of-3 extractors
+  for the 3-BRO model.  Each construction is proved to be indifferentiable from
+  a (true) random oracle where the distinguishing advantage of any
+  differentiator is upper bounded by a function of the amount of adaptivity of
+  backdoor queries---i.e. the number of times the adversary is allowed to
+  switch between backdoor query oracles---and the amount of leakage induced by
+  each backdoor query.
+
+* a restriction of the indifferentiability definition in which only a single
+  backdoor query for each RO is allowed in a preprocessing phase (this
+  definition comes in two flavor: one with two independent oracles, and one
+  with a single oracle but where salting is used). In this definition, the
+  distinguishing advantage of any differentiator is shown to be related to the
+  distinguishing advantage in the original definition. This shows in
+  particular, that the xor combiner is collision resistant in the presence of
+  two independent preprocessed advice.
+
+Strengths of the paper
+----------------------
+
+* the question studied in this paper is well motivated, and relevant to the TCC
+  audience. The indifferentiability framework is a natural way to quantify the
+  security of a combiner construction and an interesting take on the BRO model,
+  which I hope will inspire further research on this subject.
+
+* the results are correct as far as I checked (I didn't carefully check the
+  analysis of the extractor-based construction in the appendix, but I believe
+  it is correct since it follows from ideas similar to the xor construction).
+  Moreover, the analysis is an elegant application (with a slight
+  generalization) of a recent decomposition technique for high min-entropy
+  sources which is proving to be a powerful tool in the analysis of
+  constructions involving random oracles and leakage. I hope this paper will
+  further popularize this technique in this area of research and more generally
+  to the TCC audience.
+
+Weaknesses of the paper
+-----------------------
+
+* the results are somewhat hard to interpret since they depend on free
+  parameters (p_1, ..., p_c). There is a "parameter estimates" paragraph (page
+  22) in which it is explained how to tune these parameters optimally, but it
+  is still hard to get a sense of the actual guarantee provided by the
+  constructions (in particular, only the query complexity is discussed, the
+  distinguishing advantage after tuning is not given). I think it would help to
+  clarify this discussion and write the final result as a formal corollary.
+
+* relatedly, it would also help to give as an illustration a corollary for
+  a specific security game (for example treating the combined object as a OWF
+  or a PRG)---although it would have to be with a restriction on the
+  adaptivity---and stating the resulting security guarantee in this game after
+  optimally tuning the parameters. This would also allow for an easier comparison
+  with the results of [BFM18].
+
+  I believe the results are incomparable since the adversary here is weaker
+  (constant adaptivity) but the indifferentiability guarantee is more general.
+  Yet, this could be stated more explicitly. In particular, it would be
+  interesting to see whether the indifferentiability guarantee here is still
+  meaningful in the presence of adversaries making the same number of queries
+  as in [BFM18].
+
+* relatedly, the "improved parameter estimates" should also be written as
+  a formal corollary and better compared with the previous paragraph. Does it
+  always provide a better guarantee? or only for very small values of c?
+
+* similarly, the application of the AI-indifferentiability result in page 30,
+  showing that the xor combiner is collision resistant in the present of
+  independent auxiliary input should be stated as a formal corollary.
+
+* more generally, the paper would strongly benefit from a careful proofreading.
+  See the next section for a (far from exhaustive) list of small technical
+  accuracies and typos and additional comments on the presentation.
+
+Typos, comments on the presentation
+-----------------------------------
+
+* section 2.1. It is important to clarify that the backdoor oracle Bd_i takes
+  as input an arbitrary function f. And that crucially this function is allowed
+  to be different for each query performed by the adversary.
+
+* it is not clear why the original decomposition lemma is given in Appendix A,
+  since Lemma 1 in the body is a strict generalization whose proof is
+  self-contained and makes no reference to the original lemma. Furthermore, the
+  proof of the original lemma in the appendix seems to have been hastily
+  adapted from the more general one, with some inconsistencies (for example in
+  the original lemma, the set I of fixed locations is not returned by the
+  decomposition algorithm).
+
+* the statement of lemma 1, with inequalities for "some" parameters delta and
+  p is slightly confusing. Couldn't it be more simply stated by saying that the
+  distribuctions are (p, 1-delta) dense with p = p_prv + p_frsh and  delta
+  = d_prv.[big expression], i.e. with equalities instead of inequalities?
+
+* page 10, "The analysis is similar to the proof of Lemma 2". I think the
+  pointer to Lemma 2 is incorrect.
+
+* page 10, first equation of item 1 in the proof of Claim 1: I believe the
+  distribution of F shouldn't be the same on both sides of the equal sign. On
+  the left-hand side, it is indeed \mu_z|D_i, on the right-hand side, it should
+  be \mu_z (this is by definition of \mu_z|D_i.
+
+* page 10, second equation of item 1 in the proof of Claim 1: misplaced bracket
+
+* "parameter estimates" paragraph, first equation: I believe it should be
+A = N instead of A = N/log M. Similar comment for the "improved parameter
+estimates" paragraph.
+
+Summary of recommendation
+-------------------------
+
+I believe this paper will be a valuable contribution to TCC 2020 after
+a careful proofreading pass and attempt at improving the exposition as
+suggested above. I recommend acceptance.