1
$\begingroup$

We know that OWF $f$ such that none of its bits are hardcore exists. We also know that given an algorithm that solves a problem with non-negligible probability, we can repeat it many times and take the majority of the answers. Now, to predict $x$ given $f(x)$, we define predictors $P_i$ for $i$ ∈ $[1..n]$, where $P_i$ predicts the $i$th bit of $x$ with non-negligible probability. We would like to guess all n bits by running $P_1.....P_n$ several times each and taking the majority for each bit.

I want to know does this contradicts the definition of $f$?

$\endgroup$
1
$\begingroup$

No it doesn't.

The problem with the approach you suggest appears if you write down formally what you suggest: you want to repeat many times each predictor, and evaluate a majority over their predictions. However, the randomness must be taken over a random choice of input. Your predictors give approximately good answers, when averaging over all inputs to $f$. This means that there is no way to implement the strategy you suggest for a fixed input $x$.

Essentially, you can imagine a OWF where each $i$th bit predictor would give a good answer for a non-negligible fraction of the inputs (say, some subset $S_i$ of the domain of $f$), but that does not mean that inputs from $S_i$ are inputs for which the other predictors will give good results.

Here is a quick counter example: suppose that we have a length-preserving OWF $g$, with domain $\{0,1\}^n$, whose outputs are uniformly distributed. You can construct such a function easily using a PRG, which in turn can be based on any OWF. Now, let $f$ be defined as follow: consider a natural ordering of the bitstrings in $\{0,1\}^n$, and divide the domain in $n$ blocks $(B_1, \ldots, B_n)$, each containing $2^n/n$ strings. On input $x$, we define $f(x)$ to be the value obtained by replacing the $i$th bit of $g(x)$ by $0$ if the $i$th bit of $x$ is $0$, where $i$ is the index of the block $B_i$ that $x$ belongs to.

I claim that $f$ is one-way if $g$ is. Here is why: on a challenge $y$, given access to an algorithm $A$ that inverts $g$ with non-negligible probability, call $A$ on all values $(y_0,\ldots,y_n)$, where $y_i$ is obtained by replacing the $i$th bit of $y$ by $1$ (and $y_0$ is just $y$). When receiving $A$'th answers $(x_0,\ldots,x_n)$, evaluate $f$ on $(x_0,\ldots,x_n)$; if one of the evaluations (say, on $x_i$) returns $y$, stop and return $x_i$; otherwise, return $\bot$. As one of the $y_i$ is exactly the correct output of $g$ on a preimage of $y$ by $f$, it is easy to see that the probability of successfully inverting is exactly the success probability of $A$.

I claim that there are predictors $P_i$ predicting the $i$th bit of $x$ with non-negligible probability. $P_i$ simply works as follows: on input $y$, return the $i$th bit of $y$. Why does it work? Because a random input belongs to $B_i$ and has his $i$th bit equal to $0$ with probability $1/2n$, in which case the $i$th bit of the output is $0$ and the predictor always succeeds. Otherwise, the $i$th bit is uniformly distributed and the predictor succeeds with probability $1/2$, hence it has non-negligible success probability overall.

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