1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
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.
|
