Basic N$-$time Design: Let$$s assume we have N distinct HORS private$/$public key pairs all generated from one random

seed value z$.$ This can be done with various means, for example, by deriving i$$th key pair from the main seed as

zi $=$ H$($r$||$i$),$ and then deriving all other components of private$/$public key pair from zi by using zi as the input of

PRNG$.$ As is$,$ this design requires the verifier to store N distinct HORS public key after the key generation.

Achieve Basic O$(1)$ PK size Design with a Trade$-$off: Can you design a simple algorithmic approach that enables

O$(1)$ public key storage, but with a trade$-$off imposing Log$2($N$)$ signature size and signature generation blow$-$up

$($increase$)?$

For instance, in the above basic N$-$time design, the signer would only derive a small set of private key components

and sends exactly one HORS signature to the verifier for each signing operation. However, there is indeed a simple

way, in which you can make key generation such that the verifier will have only one small public key $($i$.$e$.,$ just one

hash value!$),$ but then the signer always must perform Log$2($N$)$ computation and send Log$2($N$)$ keying material

$($e$.$g$.,$ partial keys and signature$)$ over the network. Note that, initially, please assume that the signer keeps each

$($PK$1,...,$ PKN $)$ in memory so that Log$2($N$)$ computation becomes possible. Of course, if you want, you can also

discuss how much computation is required if the signer only keeps root seed z$.$ You can notice that either way, the

transmission overhead is always bounded by Log$2($N$).$

Please describe your algorithms by providing the necessary steps to show, how you transform $$Basic N$-$time

Design$$ into $$O$(1)$ PK size with Log$2($N$)$ Signer Overhead Trade$-$off$.$ You must describe your notation and steps

in sufficient detail for the algorithm to be clearly understood.

Hint: You already used such a technique in your previous assignments! For example, you can initially assume

there are only $8$ HORS sk$/$PK pairs at the signer. After this, imagine, how could you obtain only one hash value

from those $8$ PKs and give it to the verifier $($draw on a piece of paper$)?$ And finally, how can you make the verifier

authenticate it with only sublinear transmission? When you figure it out with just $8$ elements, you can then write an

algorithm to describe your solution in a more formal way $($generalized for N values$).$ Remark that you must write

an algorithmic description, not a mere verbal high$-$level description to earn credits. Your algorithm should have a

key generation $($offline$),$ signing $($online$),$ and verification $($online$).$ These three algorithms give already a clue which

technique will be used together with HORS signature