$($S$/$key Identification Scheme$)$

In the setting of one$-$time passwords, we have a client and a server that share a key, and the client has to prove his identity to the server. If an adversary can somehow steal the key from the server then all is lost. This is what happened to RSA$$s SecureID due to a hack at Lockheed Martin.

The S$/$Key identification scheme is an alternative to one$-$time passwords in which the client and server have different keys Kc and Ks$,$ and the server key is public.

To set up the scheme, we generate a random string L $$$ $\{0,1\}$k $($where k is sufficiently large, say k $>=128).$ Let H be a cryptographic hash function $($e$.$g$.,$ HMAC$-$SHA$-256).$ Let Hn denote the n$-$th iteration of H$,$ that is$,$ H$1($x$)=$ H$($x$),$ and Hi$($x$)=$ H$($Hi$1($x$))$ for every i $>=2.$ Then, the client key is Kc $=($L$,$ n$),$ and the server key is Ks $=$ Hn$+1($K$)$ for some integer n $>0.$

The scheme is then stateful $($i$.$e$.,$ both the client and the server update Ks and Kc respectively$).$ Concretely, upon running on input key Kc $=($L$,$i$)$ for $1<=$ i $<=$ n$,$ the client sends t $=$ Hi$($L$)$ to the server, and sets Kc $=($L$,$ i $1).$ If i $=0,$ the client does not do anything.

a$)$ Given a verifier key Ks and a token t$,$ how should the server validate it$?$ How should it update the key Ks$?$

b$)$ Explain informally why $$ assuming H is a good hash function $$ S$/$Key is a secure identification scheme against eavesdropping attackers.

c$)$ How would you choose the value n$?$ Explain your choice.