Let us consider Variant IV which we discussed in class. Let H be SHA$-512$ and seed x

$$ be used to derive the first

private key $($x

$1$

$1,0$

$,$ x$1$

$1,1$

$).$ Our question starts from this key. You can run hash$-$chain $$horizontally$$ by applying H

once to both key components $($x

$1$

j$+1,0$

$,$ x$1$

j$+1,1$

$)$ H$($x

$1$

j$,0$

$,$ x$1$

j$,1$

$)$ for j $=1,2,...,256($i$.$e$.,$ each private key component

for zero and one are $256-$bit$).$

Similarly, you can run hash$-$chain $$vertically$($x

i$+1$

j$,0$

$,$ xi$+1$

j$,1$

$)$ H$($x

i

j$,0$

$,$ xi

j$,1$

$).$ Given these notations as a reminder and

starting point of $($x

$1$

$1,0$

$,$ x$1$

$1,1$

$).$

Note: You must briefly explain your answer for each sub$-$question, how did you come up with it$?$ For example, you

must explain how many H operations are done in each step, how many items are transmitted, etc. Answers without

a proper explanation will receive no credit.

A$.$ Let$$s assume one H call costs $3$ msec and we want to create a public key that can be used up to K $=1024$

times.

i$)$ What is the execution time generating the public key that can be used K$-$times $($msec$)?[5$ pt$]$

ii$)$ What is the size of this public key in terms of KB $($Kilobyte$)?[5$ pt$]$

$1$

B$.$ Let$$s assume one H call costs $2$ msec and the signer computed $360$ Lamport signatures until now. Further,

assume the signer only maintains the first private key for O$(1)$ compactness purpose, and the verifier also only

stores the final public key $($i$.$e$.,$ the one originally given to him for K $=1204).$

i$)$ What is the execution time of computing $361$th signature for the signer $($it starts from scratch$)?[5$ pt$]$

ii$)$ What is the execution time of verifying $361$th signature for the verifier? $[5$ pt$]$

iii$)$ What is the size of $361$th signature in terms of KB$?[5$ pt$]$