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
|
Summary of the paper
--------------------
A "random system" is a system which adaptively and randomly answers queries
generated by an environment. Formally, a random system is defined by a sequence
of conditional probability distributions, specifying at each time step, the
distribution of the next answer conditioned on the previous (query, answer)
pairs and the new query. The contributions of this paper are as follows:
* (Section 3): it is observed that random systems can be alternatively
described in terms of "probabilistic discrete systems":
1. A "deterministic discrete systems" is defined as a function mapping
a sequence of queries to an answer. An "environment" is a function
mapping a sequence of answers to the next query. The transcript of an
interaction between a "deterministic discrete system" and an
"environment" is the sequence of (query, answer) pairs obtained by
iteratively feeding queries generated by the environment from past
answers to the system.
2. A "probabilistic discrete system" is then defined as a distribution over
"deterministic systems". Finally
3. A random system is exactly an equivalence class of "probabilistic
discrete systems" where to discrete systems are equivalent iff they
induce the same transcript distribution for all environments.
* (Section 4) a "coupling lemma" is established, showing that the maximum
distinguishing advantage between two random systems S and T is exactly the
minimum statistical distance between S' and T' where S' (resp. T') is
a "probabilistic discrete system" in the equivalence class defined by
S (resp. T).
* (Section 5) it is shown how to use the coupling lemma of Section 4 to prove
an indistinguishability amplification theorem for neutralizing constructions.
While the theorem is not new, the proof is made much simpler than what
previously known by the use of the coupling lemma. A generalization of this
theorem to "q-neutralizing" constructions in then stated without a proof
(with a reference to prior work).
Strengths
---------
* The paper gives a nice characterization of the maximum distinguishing
advantage between two random systems, leading to a very clean and short proof
of the amplification theorem for neutralizing constructions.
This is in nice contrast to the status quo in cryptography where complex
interactive protocols are hard to analyze formally without introducing
hard-to-read notations, which is (understandably) rarely done, but
unfortunately often leads to a lack of rigor.
* The paper is very clear and well written.
Weakness
--------
* The paper is perhaps somewhat lacking in terms of novelty since it can be
thought of as providing a new proof of a known result and it is not
completely clear whether the coupling lemma is broadly applicable.
Comments
--------
* Lemma 2.2: state that the joint distribution X can also be chosen so
that its weight is p. This property is used later in the paper (see the next
comment).
* Proof of lemma 4.4: the last displaymath equation implicitly uses that the
joint distribution E has weight tau. This should be stated explicitly as
a consequence of lemma 2.2 after modifying it as suggested in the previous
comment.
* Proof of Theorem 5.5: I would suggest removing the word "sketch" qualifier
and adding a couple sentences to justify each step in the chain of
(in)equalities.
* I suggest removing section 5.3 entirely. It is claimed in the introduction to
this section that the coupling lemma can be used to prove Theorem 5.9. This
would be a nice illustration of the techniques introduced in this paper, but
unfortunately, the theorem is stated without its proof (with only a reference
to previous work). As a result, it seems that this section could be reduced
to a remark below Theorem 5.5, stating that "The coupling lemma can also be
used to prove an amplification theorem for q-neutralizing constructions as is
done in [4]".
Summary of recommendation
-------------------------
While the paper is perhaps not very "innovative", it introduces a refreshingly
simple approach to rigorously analyzing indistinguishability games involving
interactive systems. I am leaning towards acceptance.
|
