path: root/tcc-2019-232.txt

Overall grade: 5
Confidence level: 3
Technical: 3
Editorial: 1

Summary of the paper
--------------------

This paper considers the problem of building pseudorandom functions (PRF) from
non-adaptive pseudorandom functions (naPRF). The main result rules out the
existence of a fairly general class of one-call fully black box constructions
(in the sense of [RTV04]). Specifically, the authors consider constructions
with the following structure:

1. a (possibly seeded) preprocessing function is applied to the input

2. the preprocessed input is fed to the naPRF, importantly (and this
   is the only real restriction compared to arbitrary one-call constructions)
   the seed used in computing the naPRF is a uniform random variable
   independent of the input, i.e. it is what the naPRF "expects" as a seed

3. a (possibly seeded) post-processing function is applied to the output of the
   naPRF

The proof of the main result uses the standard fact that fully black-bock
constructions relativize: for a one-call construction F of the type described
above, the authors construct an oracle relative to which a naPRF exist but for
which F is not secure against adaptive adversaries. This oracle is similar to
the oracle constructed in (Myers 2004) and can be informally described as
follows:

1. the first part of the oracle is a uniformly random (seeded) oracle O, which
   in particular is an exponentially strong PRF

2. the second part of the oracle, R, acts as an "inverter" for F, but *only* to
   an adversary which is able to prove that it is making adaptive queries to F

The authors then proceed to prove that relative to (O, R):

1. O is a naPRF. This is the most challenging part and requires showing that
   a non-adaptive adversary cannot take advantage of R. This is achieved by
   showing how, to a non-adaptive adversary, R can be (approximately) simulated
   efficiently.

2. F instantiated with O is not a PRF. This part is fairly straightforward
   since R was designed specifically to break F^O.

The above proof is only valid when the preprocessing function satisfies
a "universality" property. In the last part of the paper, the authors show how
this restriction can be removed in specific cases.

Strengths
---------

* The question of building PRFs from naPRFs is important and this paper nicely
  complements a small set of results ruling out natural classes of
  constructions.  In particular it shows that the one-call construction of
  (Berman, Haitner 2015) cannot be proved secure in a black-box manner when the
  naPRF is only secure to PPT adversaries.

* The class of one-call construction which is introduced in this paper is
  interesting. In particular, the authors convincingly show that a subtle
  interplay between the pre-processing and post-processing functions requires
  both a careful analysis and additional assumptions (like c-universality).

Weaknesses
----------

* Simply ruling out one-call constructions is arguably restricted. The authors
  make a convincing case that this is already non-trivial and progress compared
  to what is already known. However, it could have been nice to explain in
  greater detail the main challenges in extending this result to arbitrary
  constant number of calls.

* The paper seem to have been put together rather hastily and would benefit
  from a thorough proofreading pass (more on this below).

Technical inaccuracy
--------------------

1. Although I am quite confident that the results and proof is correct, it seems
that there is an inaccuracy in the proof:

* it starts in Definition 5, p. 13 where the definition of the good seeds
  requires |C(s, X_1)| > l/(c-1) (and similarly for X_2 and X). This is
  inconsistent with the informal description given above the definition which
  requires that there is no c-way collision in C(s, X_1). Note that the absence
  of a c-way collision implies |C(s, X_1) > l/c-1) but the converse it not
  true. 

* the previous point becomes problematic in appendix E.2 (proof of Lemma 12),
  where it is claimed that |C(s, T_1)|> l/(c-1) implies that when considering
  a subset I of l/2 indices, there must be at least l/2(c-1) distinct values in
  |C(s, T_1[I])|. This is not true, since C(s, T_1) could for example comprise:

  * l/(c-1) distinct values in the first l/(c-1) indices
  * the same value repeated in the next l - l/(c-1) indices

  Clearly, the set containing the last l/2 indices will not have the desired
  property (for, say, c greater than 4)

For this reason, I believe that Definition 5 should be fixed to reflect the
original intended meaning (absence of c-way collision). Then, the entire proof
should go through after replacing all the instances (not just in appendix E.2)
of the clause "|C(s, X)|> l/(c-1)" by the clause "there is no c-way collision
in C(S, X)". And only using that "|C(s, X)| > l/(c-1)" when necessary as
a property implied by the absence of a c-way collision. 

In particular, Definition 12 (Badf) and the Proof of Lemma 15 (p. 34) needs to
be fixed in a similar manner.

Comments on the presentation
----------------------------

Although the general structure is good, the paper suffers at times from
inconsistencies and redundancies which interfere with the flow of the paper:

* the security parameter is called lambda in the introduction, but then it
  seems that n plays the role of lambda (or is it n+sigma?)

* the class of one-call constructions considered in the paper is described
  three times, which is at least one too many. I suggest the one at the
  beginning of section 2.1 be removed.

* beta-sparse and beta-good are used quite inconsistently. In particular, in
  section 2.2, an informal description of a beta-good seed is given, but the
  description given turns out to correspond to what is later defined as
  beta-sparse. However, section 2.2 does require the notion of beta-good to be
  correct.

* the choice of name 1/2-good for elements in the co-domain of G is
  questionable since it could be confused with the notion of a beta-good seed.

* the formalism of function families in section 3 is unnecessarily complicated:

  - splitting F into two functions F.Kg and F.Eval is unnecessary since in all
	cases considered in the paper the key distribution is uniformly random.
	I recommend having only F taking as input a uniformly random key. In fact,
	this is how it is done in most places in the proof, and the function F.Kg
	is not used consistently.

  - the functions do not need to take 1^n as an extra input since it can be
	inferred from the key length. In fact, this input is already dropped in
	most places, so I would recommend not introducing it at all.

* the notation H^O for the naPRF in the relativized world seems unnecessary
  since it is just a different name for O

* the overview in Section 2.2 is quite confusing and only became clear after
  reading the formal proof:

  - throughout it says that the oracle R provides requests or challenges. This
	is counterintuitive since we usually think of an oracle as something which
	is queried, not the converse. It could make sense to, already at this
	stage, describe the "three-part" structure of the oracle, whose first two
	parts effectively can be thought of as providing challenges.

  - introducing the three-part structure would also be a good way to explain
	that the oracle is designed to force the adversary to make adaptive queries
	by committing to a value y before receiving the input to the next query. At
	the moment this point is a bit lost in the overview and only described by
	the somewhat cryptic "R issues x_{i+1} only after learning y_i".

* the flow of the proof is a bit hard to follow since it is split in many
  lemmas with many forward pointers. I wonder whether some re-ordering could
  make it easier to follow.
  
* the proof could also be factored better: I believe the goal of Lemma 4 is to
  factor out parts of the proof, but it does not quite achieve this goal. For
  example the proof of Lemma 12 is extremely similar to the proof of Lemma
  4 but does not use it. Also, whenever Lemma 4 is invoked, the preliminary
  work to invoke it is identical, so I suspect that even more could be factored
  out with a slightly more general lemma.

* The quantity 2l/4c which appears frequently should be simplified to l/2c.

* Lemma 11: I believe the factor q is unnecessary since there is at most one
  query where X_2 is sampled. So instead of a union bound, it seems that one
  could the disjoint events "X_2 is sampled at query i" for i in {1, ..., q}.

Typos and minor inaccuracies
----------------------------

The following list is far from being exhaustive:

* Section 1, paragraph "The BH approach", single-line equation: k should be
  replaced by s

* Section 1, paragraph "Our results in detail": "which often requires the input
  to H to (be) fresh" (missing word)

* Section 2.2, paragraph "Security of H revisited": "considering only
  beta-goods" --> "considering only beta-good seeds"

* Section 2.2, paragraph "Security of H revisited", last sentence:
  "beta-sparse" --> "beta-good" (see also above comment on inconsistent use of
  beta-sparse/good)

* Section 4.2, last paragraph: "closely to related to" --> "closely related to"
  (extra "to")

* Section 4.2, last paragraph: "the challenge in the" --> "the challenge"

* Section 4.3, first paragraph: "Putting Propositions 1 and 2 (together)"
  (missing word)

* Section 5.4, first paragraph: "The challenge is (to)" (missing word)

* Appendix D: the set Q^* which is used throughout has not been formally
  defined. In particular, Fig. 4 should show how it is computed.

* Proof of Lemma 11: beta-good should be replaced by beta-sparse throughout

* Proof of Lemma 11: both products should be indexed starting from i=0

* "Proof overview" of Lemma 14: "of size at least l(k+1)/2c(c-1)", the k should
  be replaced by c

* "Proof overview" of Lemma 15, last single-line equation: there is a missing
  2.sigma multiplicative factor in front of the last summand

* Appendix E.2: "it must be that there are at least l/2(k-1)", the k should be
  replaced by c

* Appendix E.2: "of the Z_1[i]'s (Let Z_1[i])" some extra words should be
  removed

* Appendix E.2: "where t = |J_s| \geq l/2c - l/2(c-1)" it should be "l/2(c-1)
  - l/2c"

* Proof of Lemma 14, last line: t= l(c+1)/2c(c-1) (there is a missing (c+1)
  factor)

* Proof of Lemma 15: what is proved is an upper bound  on Pr[Bad_2 and
  j < t | not Bad] (and similarly for j > t + p -1). In other words, the
  condition on j should be put on the left-hand side of the conditioning.

* Appendix G, equation (17): l^* and delta do not exist in this context.
  delta*l^* should be replaced by l/c

Summary of recommendation
-------------------------

The problem and the results are interesting. I believe this paper will be
a valuable contribution to TCC if the above comments are addressed and after
a thorough pass of proofreading.