Add ITCS 2020 review

1 files changed, 94 insertions, 0 deletions

diff --git a/itcs-2020-136.txt b/itcs-2020-136.txt
new file mode 100644
index 0000000..c8cfc55
--- /dev/null
+++ b/itcs-2020-136.txt
@@ -0,0 +1,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.