# Tag Info

0

Actually the proof that $h$ is one-way is not that trivial... First, a reminder on definitions. A function $f$ is (strongly) one-way if for all probabilistic polynomial-time adversaries $A$, all polynomials $p$ and all sufficiently large $n$, we have $$\mathrm{Pr}[A(f(U_n),1^n) \in f^{-1}(U_n)] < \frac{1}{p(n)}$$ (where $U_n$ represents a random variable ...

0

Actually, $h(x)$ is one-way. Probably what puzzles your intuition is, that the definition of one-way functions is an asymptotic statement over a whole family of functions indexed by $n$. Proof (scetch): Assume $h(x)$ is not one-way. This means, there exists an algorithm $A$, which for uniformly chosen $x$ calculates a preimage $x_0$ to $h(x) = y \| x_n$ ...

0

A probabilistic algorithm uses random numbers to define the next step it should do (google for instance "Monte Carlo Algorithm"). "Random coin tosses" merely says that the random numbers are equally distributed. The algorithm A will use the random numbers only internally, it will not output any random number. But A's output will depend on those random ...

0

(For that definition, one will also need that $\hspace{.04 in}f\hspace{.02 in}$'s outputs are not too much shorter than $\hspace{.04 in}f\hspace{.02 in}$'s inputs.) It means "random bits generated by A". $\:$ For example, A might be flip 7 coins if exactly 5 of those come up heads: output 011101 else: output 100010 .

3

I assume that $|x|$ in the exercise denotes the length of the bitstring $x$. If so, the answer is simple: a polynomial time algorithm needs to complete in a number of steps bounded by a polynomial function of the length of its input. How long is $|x|$, represented as a bitstring? Well, it takes $k$ bits to represent a number between $2^{k-1}$ and $2^k-1$, ...

Top 50 recent answers are included