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 the 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
* improves on state of the art algorithms
* 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 a 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 model 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 a bit lost in the proof at
  the moment but could maybe be factorized 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 spawn
interesting future research.