# Completeness of formal definition of 'hardness on the average'

While reading a cryptography textbook, i find the definition of a function that is hard on the average.(More precisely, it is 'hard on the average but easy with auxiliary input', but i omit latter for simplicity.)

Definition : Hard on the average :

$$h:\{0,1\}^*\to \{0,1\}^*$$ is hard on the average if there exists a probabilistic polynomial-time algorithm $$G$$ such that
for every probabilistic polynomial-time algorithm $$A'$$ every positive polynomial $$p(\cdot)$$, and all sufficiently large $$n$$'s, Pr$$[A'(X_n)=h(X_n)]<\frac{1}{p(n)}$$

where $$X_n := G(1^n)$$ is a random variable assigned the output of $$G$$.

My question is why the statement of the existence of qualified algorithm G is sufficient?

In other words, why the above definition gives a formal definition of 'hardness on the average' instead of following definition, which is more intuitive(?) to understand and more strict. Why is the above definition sufficient?

( Now I'm thinking that problem might occur when $$G$$ has only polynomial number of possible outputs, but if so, let's replace 'for any $$G$$' with 'for any $$G$$ which have exponentially many possible outputs' in following definition.)

(strong?) Def : Hard on the average :

$$h:\{0,1\}^*\to \{0,1\}^*$$ is hard on the average if for any probabilistic polynomial-time algorithm $$G$$ and for every probabilistic polynomial-time algorithm $$A'$$ every positive polynomial $$p(\cdot)$$, and all sufficiently large $$n$$'s, Pr$$[A'(X_n)=h(X_n)]<\frac{1}{p(n)}$$

where $$X_n := G(1^n)$$ is a random variable assigned the output of $$G$$.

Another question is that whether a following simpler definition is equivalent to original definition or not?

(simple) Def : Hard on the average :

$$h:\{0,1\}^*\to \{0,1\}^*$$ is hard on the average if for every probabilistic polynomial-time algorithm $$A'$$ every positive polynomial $$p(\cdot)$$, and all sufficiently large $$n$$'s, Pr$$[A'(U_n)=h(U_n)]<\frac{1}{p(n)}$$

where $$U_n$$ is a random variable uniformly distributed over $$\{0,1\}^n$$.

Hard on average is sometimes defined as in your third (simple) definition: a function $h$ is hard on average if on a uniformly random input, its output cannot be predicted by a ppt with more than a negligible probability. The first definition also captures the situation in which the "correct" input distribution is different. For example, consider the function $$h(xy) = \begin{cases} H(x) & y = 0, \\ 0 & y \neq 0, \end{cases}$$ where $|x| = |y|$ and $H$ is some hard-on-average function (under the simple definition). The function $h$ is not hard on average under the simple definition, but it's hard on average under the more complicated definition. I'm not sure why we should be interested in such functions, but there's probably a reason. You'll have to continue reading and reflect when the more complicated definition is needed.
As for your second definition, it is far too strong. Consider for example what happens if $G$ always outputs the zero string. You are still capturing something - the halting function will still be hard - but there's no notion of "average". You have indeed anticipated this in your comment (though it only really applies in the non-uniform setting), but the resulting notion is still probably too strong.
• You claim that if $G$ has a few (polynomially) many outputs then it's easy to predict any function. However, in general this is not true: for example, perhaps $h(x)$ indicates whether the $|x|$th program halts or not. However, in the non-uniform setting (a polynomial size circuit or a ppt with polynomial advice), this argument does work - your predictor can be given all the values of $h$ on the range of $G$. – Yuval Filmus Aug 9 '13 at 3:35