# Hard-core predicates: should the adversary be given $1^n$?

In most (all?) classical sources such as the book of Goldreich (2001), hard-core predicated are defined thus:

A polynomial-time computable predicate $b : \{0,1\}^* \to \{0,1\}$ is a hard-core of a function $f$ if for every probabilistic polynomial-time (PPT) algorithm $A$, every positive polynomial $p$ and all sufficiently large $n$, $$\mathsf{Pr}\left[A(f(U_n)) = b(U_n)\right] < \frac{1}{2} + \frac{1}{p(n)}.$$

However, in the more recent book of Katz and Lindell (2015 for the second edition), $A$ is also given $1^n$. This seems to make a difference, for example for the following exercise:

Show that any injective, polynomial-time computable function which has a hard-core predicate is one-way.

Under the Katz-Lindell definition of hard-core predicates, this is trivial: given a PPT adversary $A$ which can successfully invert such a function $f$, we construct a PPT adversary $B$ which can successfully compute any predicate $b$ for $f$ as follows. On input $(y, 1^n)$, $B$ runs $x' \gets A(y, 1^n)$ and outputs $b(x')$ if $f(x') = y$ and a random bit otherwise.

However, if $B$ is not given $1^n$, then it is not clear to me that it can determine in polynomial time the correct value of $n$ on which to run $A$. Goldreich also gives this exercise, but adds that "you may assume for simplicity that $f$ is length-preserving", which again makes it trivial.

In general, giving $1^n$ to the adversary seems to make the situation simpler, mainly because it makes the definition of hard-core predicates mirror that of one-way functions more closely, and if we assume (as is common) that $f$ is length-preserving, it is just redundant. I guess my question is: is there currently any consensus among researchers in this regard? Or are the two definitions actually equivalent (in which case I probably need to give in more thought...)?

• $B$ can just run $A$ with $n$ ranging from $0$ to $\:2\hspace{-0.03 in}\cdot \hspace{-0.03 in}\operatorname{length}(\hspace{.03 in}y)\:$,$\:$ since injective functions have negligible probability of shrinking random inputs by large amounts. $\;\;\;\;$
– user991
May 22, 2015 at 11:27

First note that it is not necessary for $B$ to guess the correct $n$. To see this, you can think of the PPT adversary $A'$ that on input $(y, 1^{n-1})$ outputs $A(y, 1^n)$. The sole purpose of the input $1^n$ is to allow $A$ to run in polytime in $n$.
However, if the input (i.e., the output of $f$) to $B$ is of size, e.g., a constant $k$, then $B$ can not run an adversary $A$ running in polytime of $n$. But in this case it should not be problem for the following reason.
I assume $U_n$ here roughly means a $n$ uniformly random bits? In that case you have from $f$ being injective and pigeon-hole principle that with high probability (at least $\frac{1}{2}$) $|f(U_n)| \geq n$. I.e., $B$ will be allowed to run in polytime in $n$ at least on these inputs.
EDIT: Note that the above is slight sloppy and simplified argument. You do not strictly need $|f(U_n)| \geq n$, it could be smaller. You just need it to be large enough for $B$ to run in poly time of $n$.