Completeness of formal definition of 'hardness on the average'

Question

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

Answer 1

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.

The notion of hard on average came out of an attempt to proof the security of some notion. While it is indeed meant to capture some intuitive sense of hardness on average, the details were determined from some argument who used them, from some construction that obtained them; they're not arbitrary. These notions have been found to be useful, which is why they continue being used. Your suggested notion might be helpful as well, but the onus of proof is on you.