S$/$Key system$]$ Define the hash chain as follows. For an input $$x$$ and a cryptographic hash

function $$H$,$ we write H$($x$)$ as an output of $$H$$ on input $$x$,$ then H$(2)($x$)$:$=$H$($H$($x$)),$ H$(3)($x$)$:$=$H$($H$($H$($x$))),$

and so on$.$ Assume that $$H$$ is hard to invert, even after $$n$$ iterations.

Recall that in the S$/$Key identification system, the key generation works as follows: choose a random

bit$-$string $$k$($for certainty, let its length be $256$ bits$),$ then set a verification key vk $=$ H$($n$+1)($k$)$ for

some integer $$n$($for certainty, let n$=100)$ and set a secret key sk $=($k$,$n$).$

Task: Explain how this identification scheme works $(5$ points$)$ and why it is secure$,$ in particular why

$$vk$$ can be public $(5$ points$).$