4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ $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. $\;\;\;\;$ $\endgroup$ – user991 May 22 '15 at 11:27
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.