diff options
| -rw-r--r-- | tcc-2020-153.txt | 135 |
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. |