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
|
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.
|
