diff options
| -rw-r--r-- | tcc-2019-120.txt | 110 |
1 files changed, 110 insertions, 0 deletions
diff --git a/tcc-2019-120.txt b/tcc-2019-120.txt new file mode 100644 index 0000000..21bbd3d --- /dev/null +++ b/tcc-2019-120.txt @@ -0,0 +1,110 @@ +Grades +------ + +Overall: 4 +Confidence: 3 +Technical: 2 +Editorial: 3 + +Summary of the paper +-------------------- + +This paper studies the function inversion problem in cryptography: given oracle +access to a function f, an adversary: + +1. computes S bits of preprocessed advice +2. given challenge y in the co-domain of f, by making at most T queries to + f, and using the preprocessed advice, the adversary must compute x such that + f(x) = y + +Characterizing the set of pairs (S, T) for which such adversaries exist is +a major open problem in cryptography. The best known lower bound is ST += Omega(N) and the best known upper bound is S^3 T = O(N^3). + +This paper sheds light on this problem by connecting it to various other +questions in (communication) complexity and data structures. Specifically, the +authors establish the following: + +* connection between strongly non-adaptive adversaries and circuits in the + common-bits model. This connection show that small improvements on the ST + = Omega(N) lower bound would imply, depending on the regime of parameters + + - if S is very close to N: an explicit boolean operator whose hardness to + circuits in the common-bits model would improve best known lower bounds in + this model + + - if S = N^{1/2+eps} for constant eps: an explicit boolean operator which + cannot be computed by log depth circuits, thus resolving a major open + question in circuit complexity + +* a connection between inverting one-to-one function and breaking the security + of PRGs (in the black-box model). This connection shows that thinking about + the one-to-one case could be an interesting intermediate step between + permutations and arbitrary functions. + +* a connection between inverting permutations and solving the permutation + variant of the pointer jumping problem in the number-on-the-forehead model of + communication complexity. Using Hellman's algorithm, this connection leads to + an improvement on the best known algorithm for this problem. + +* a connection between the function inversion problem and data structure + problem of substring search. Using the Fiat-Naor algorithm, this connection + implies an algorithm which improves on the best-known algorithms for the + substring search problem. + +Strengths +--------- + +The paper +* sheds light on why improving the ST = Omega(N) lower bound is hard +* is very clear, well-written and a pleasure to read +* contains many interesting observations and suggestions for future research + +Weaknesses +---------- + +* The connection between function inversion and distinguishing PRGs only holds + relative to a random oracle. It is not clear to me how much this weakens the + conclusion and the authors say very little about it. + +* The paper is a juxtaposition of disparate facts, many of which are not + particularly surprising and follow from fairly standard arguments. It would + be nice to have stronger conceptual message connecting the dots. + + +Comments on the presentation +---------------------------- + +* I think section 2 could make a better job at emphasizing that strongly non + adaptive adversaries with oracle access to a function f are nothing but + circuits in the common-bits in disguise (the value table of f plays the role + of the circuit input, the preprocessed string are the common-bits and the + input to the adversary indexes into the output bits of the circuit). There is + a strict syntactic equivalence which is lost in the proof at the moment but + could maybe be abstracted away in a lemma? + +* The proof idea in section 2.2 is basically the same length as the full proof + so I would suggest simply replacing it with the proof given in the appendix. + The full proof is clearly written so it is not clear that a proof overview + (of the same length) is helpful. + +* Similarly, the proof idea below Lemma 9 might as well be replaced by the full + proof. + +Minor comments +-------------- + +* appendix D: it should be made clear that the permutations pi_j and sigma_j + derived in the preprocessing and online phases are the same. + +* appendix D, description of the online phase: \hat{b_i} is the majority vote + of {b_{i1}, ... , b_{ik}} (the indices are incorrect) + +Summary of recommendation +------------------------- + +I am leaning towards acceptance. While some of the contributions are not +particularly surprising and the whole lacks a bit of coherence, the paper does +improve on state of the art algorithms, sheds light on the important function +inversion problem and has the potential to draw attention to it and trigger +interesting future research. |