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.