## 3 Multivariable Polynomial Signature Schemes
### LUOV Scheme
#### 3.2.1 The Reference Implementation  
Algorithm 1 shows a pseudo-code representation of the \(C\) code of the key generation algorithm from the reference implementation for LUOV [1]. First, it randomly generates private_seed that is stored in a byte array of length 32. The subsequent calls uses private_seed as input to an extendable function \(\mathcal{H}\), which is either SHAKE128 or SHAKE256, to generate public_seed, which is stored as a byte array of length 32, as well as the matrix \(T\in\mathbb{F}_{2}^{\infty\times o}\) that determines the linear map \(\mathcal{T}\), which is stored as a byte array of length \(\left\lceil\frac{o}{8}\right\rceil\!v\). The entries of such array whose indices are in the range \(\{(i-1)\lceil\frac{o}{8}\rceil+1,\ldots,i\lceil\frac{o}{8}\rceil\}\) represent the \(i\)th row of \(T\) for \(1\leq i\leq v\). If \(o\) is not divisible by 8, the most significant bits of the last byte (i.e., \(i\lceil\frac{o}{8}\rceil\)-th byte in the sequence) are ignored. ```
functionKeyGEN() //generate a random secret key (32 byte array). private_seed\(\leftarrow\)randombytes(32); //generate a 32 byte array (the private sponge) from private_seed. private_sponge\(\leftarrow\)InitializeAndAbsorb(private_seed,32); //generate a 32 byte array (the public seed) from private_sponge. public_seed\(\leftarrow\)SqueezePublicSeed(private_sponge,32); //generate the matrix \(T\) from the output of a pseudo-random generator on input private_sponge. T\(\leftarrow\)SqueezeT(private_sponge); //generate a 32 byte array (the public sponge) from public_seed. public_sponge\(\leftarrow\)InitializeAndAbsorb(public_seed,32); //generate the matrices \(\mathtt{C},\mathtt{L},\mathtt{Q}_{1}\) from public_sponge. C,\(\mathtt{L},\mathtt{Q}_{1}\leftarrow\)SqueezePublicMap(public_sponge); //calculate \(\mathtt{Q}_{2}\), the part of the public map that cannot be generated from the public seed. Q\({}_{2}\leftarrow\)CalculateQ2(\(\mathtt{Q}_{1}\),T); //return the public key (public_seed,\(\mathtt{Q}_{2}\)) and the secret key private_seed. return(public_seed,\(\mathtt{Q}_{2}\)) and private_seed; endfunction
```  
**Algorithm 1** Key Generation Algorithm for LUOV. By making \(\lceil\frac{\phi}{16}\rceil\) calls to an extendable function \(\mathcal{G}\), which is either SHAKE128 or ChaCha8, with public_seed and a salt 0x0i with \(i\in\{0,\ldots,\lceil\frac{\phi}{16}\rceil-1\}\) as inputs, the function SqueezePublicMap generates \(\mathtt{C},\mathtt{L}\) and \(\mathtt{Q}_{1}\), where  
* \(\mathtt{C}\in\mathbb{F}_{2}^{\alpha}\) is the constant part of the public map \(\mathcal{P}\) and stored in a byte array of length \(\lceil\frac{\phi}{8}\rceil\). * \(\mathtt{L}\in\mathbb{F}_{2}^{\alpha\times n}\) is the the linear part of \(\mathcal{P}\) and stored in a byte array of length \(\lceil\frac{\phi}{8}\rceil n\)
* \(\mathtt{Q}_{1}\in\mathbb{F}_{2}^{\alpha\times(\frac{\phi(1+1)}{2}+\mathtt{v} \cdot\mathtt{o})}\) is the first \(\frac{\mathtt{v}\cdot(\mathtt{v}+1)}{2}+\mathtt{v}\cdot\mathtt{o}\) columns of the Macaulay matrix of the quadratic part of \(\mathcal{P}\) in the lexicographic ordering and stored in a byte array of length \(\lceil\frac{\phi}{8}\rceil(\frac{\mathtt{v}\cdot(\mathtt{v}+1)}{2}+\mathtt{v} \cdot\mathtt{o})\). It then calculates \(\mathtt{Q}_{2}\in\mathbb{F}_{2}^{\alpha\times(\frac{\phi(\mathtt{v}+1)}{2})}\), the remaining part of the Macaulay matrix of the quadratic part of \(\mathcal{P}\), and finally returns the public key (public_seed,\(\mathtt{Q}_{2}\)) and the private key private_seed. On the one hand, the public key gets to be encoded as a byte array of length \(32+\lceil\frac{\phi^{2}(\mathtt{v}+1)}{16}\rceil\), where the first 32 bytes represent public_seed and the remaining bytes, seen as a long sequence of bits, represent \(\mathtt{Q}_{2}\) as follows: the first \(o\) bits represent the first column, the next \(o\) bits represent the second column, and so on up to complete the \(\frac{\mathtt{o}(\mathtt{v}+1)}{2}\)th column. On the other hand, the private key is the 32 byte array private_seed.