How does mutlivariate crypto schemes work?

I have been studying multivariate cryptography for post-quantum cryptography lately, but I have a hard time in understanding how these signature schemes work. As long as I see there there is UOV scheme, then Rainbow which is kind of a generalization of UOV scheme, and also there is something called HFEv-.

But how does these signature schemes work? I mean we use some multivariate polynomials, and most of the time the polynomials are quadratic. But how do we actually sign and verify messages (let's say a toy message such as 011101101)? Is there any place where I can find step by step how the algorithms work, and their application to toy examples so as to see how they work?

UOV

The first thing you need to know about UOV is that the input variables are partitioned into vinegar variables $x_1, \ldots, x_v$ and oil variables $x_{v+1}, \ldots, x_{v+o}$. The number of vinegar variables is roughly twice the number of oil variables: $v = 2o$. The name oil and vinegar comes from the fact that oil variables do not mix with other oil variables in the secret polynomials. In fact, every polynomial of the secret key can be described as a quadratic form. For example, let $v=4$ and $o=2$ and $\mathbf{x}^\mathsf{T} = (x_1 \, x_2 \, x_3 \, x_4 \, x_5 \, x_6)$. Then every secret polynomial can be described as: $$f_i(\mathbf{x}) = \mathbf{x}^\mathsf{T} \left( \begin{matrix} * & * & * & * & * & * \\ * & * & * & * & * & * \\ * & * & * & * & * & * \\ * & * & * & * & * & * \\ * & * & * & * & & \\ * & * & * & * & & \\ \end{matrix} \right) \mathbf{x} \enspace .$$ Where the $*$ indicate randomly chosen elements, but the blank spaces indicate zeros. The oil variables, $x_5$ and $x_6$ are not mixed with themselves or each other.

Now, it's also important to know that there are exactly $o$ secret polynomials. The vectorial function whose components are $f_i$ is denoted by $\mathcal{F}$: $$\mathcal{F}(\mathbf{x}) = \left( \begin{matrix} f_1(\mathbf{x}) \\ \vdots \\ f_o(\mathbf{x}) \end{matrix} \right) \enspace .$$ (In our example there are just two components in $\mathcal{F}$.)

The public key $\mathcal{P}$ is generated from $\mathcal{F}$ by composing it with a random invertible linear transformation $S \in \mathsf{GL}_{o+v}(\mathbb{F}_q)$, which is really a square matrix whose inverse exists: $S \in \mathbb{F}_q^{(v+o)\times(v+o)}$. The public key is then $$\mathcal{P} = \mathcal{F} \circ S \enspace .$$

In order to sign a document $d$ with hash $\mathbf{h} = \mathsf{H}(d)$, the signer does the following. First, choose a random assignment to the vinegar variables $x_1, \ldots, x_v$. Then the system of polynomial equations $\mathcal{F}(x_{v+1},\ldots,x_{v+o}) = \mathbf{h}$ is a linear $o \times o$ system. Solve it to obtain $x_{v+1}, \ldots, x_{v+o}$ and at this point the signer has the entire vector $\mathbf{x}$. Next, compute the signature $\mathbf{y}$ as $\mathbf{y} = S^{-1}\mathbf{x}$.

In order to verify a signature $\mathbf{y}$, the verifier evaluates the public key in $\mathbf{y}$, and checks if the result is equal to the hash of the document, i.e., $$\mathcal{P}(\mathbf{y}) \stackrel{?}{=} \mathsf{H}(d) \enspace .$$

Notice how UOV uses a linear $o \times o$ system as a step in generating signatures, but how this step generalizes to any quadratic (!) system for which it is possible to find an inverse efficiently. For instance, you can level down recursively and put another UOV system there. This multi-layer approach is called Rainbow.

HFE, HFE-, and HFEv-

HFE-type systems are very different. The first thing you should know about them is that they use univariate polynomials over the extension field. So $\mathbb{F}_q$ is the base field (like in the UOV case). Then pick any irreducible polynomial $f(z) \in \mathbb{F}_q[z]$ of degree $n$, and then you can identify the set of polynomials $\mathbb{F}_q[z] / \langle f(z) \rangle$ of degree smaller than $n$ as a new field, the extension field $\mathbb{F}_{q^n}$, whose operations are polynomial addition and polynomial multiplication modulo $f(z)$. Whenever you have a vector of $n$ values over the base field, say $\mathbf{a} \in \mathbb{F}_q^n$, you can embed this value in the extension field using the canonical embedding $\varphi : \mathbb{F}_q^n \rightarrow \mathbb{F}_{q^n} : \mathbf{a} \mapsto A = \sum_{i=1}^na_iz^{i-1}$. In particular, you can do this with the vector of variables: $\varphi(\mathbf{x}) = X$ and then you have a single variable $X$ over the extension field. Any list of $n$ multivariate polynomials in $\mathbf{x}$ over the base field maps to one univariate polynomial in $X$ over the extension field, and vice versa.

In order to generate a HFE secret key, choose a random univariate polynomial over the extension field $\mathcal{F}(X) \in \mathbb{F}_{q^n}[X]$ with degree at most $D$ and of the form $$\mathcal{F}(X) = \sum_{i} \sum_{j} \alpha_{i,j} X^{q^i + q^j} \enspace .$$ In other words, choose the coefficients $\alpha_{i,j}$ uniformly at random from $\mathbb{F}_{q^n}$ as long as $q^i+q^j \leq D$, and set $\alpha_{i,j}=0$ otherwise. Following this structure for $\mathcal{F}$ will guarantee that it maps to a list of multivariate quadratic equations over the base field. In the old days they recommended $D \approx 1000$ but now we understand how to make HFE secure with much smaller $D$, e.g. $D \approx 10$ -- and that will only make the scheme faster! Next, choose two random invertible linear transformations $T, S \in \mathsf{GL}_n(\mathbb{F}_q)$ which are once again really invertible square matrices in $\mathbb{F}_q^{n \times n}$. The secret key consists of $(\varphi, \mathcal{F}, T, S)$. The public key is found by composing these transforms: $$\mathcal{P} = T \circ \varphi^{-1} \circ \mathcal{F} \circ \varphi \circ S \enspace .$$

In order to sign a document $d$ with hash $\mathbf{h} = \mathsf{H}(d)$, the signer proceeds as follows. First, he computes $Y = \varphi(T^{-1}\mathbf{h})$. Then he uses Berlekamp's algorithm to factorize the polynomial $\mathcal{F}(X)-Y$ and find the roots $\{X_i\}$ that make it zero. He chooses one of these roots as $X$ and proceeds to compute the signature $\mathbf{z} = S^{-1}\varphi^{-1}(X)$.

In order to verify a signature, the verifier evaluates the public key $\mathcal{P}$ in $\mathbf{z}$ and checks whether he obtains the hash $\mathbf{h}$ of the document: $$\mathcal{P}(\mathbf{z}) \stackrel{?}{=} \mathsf{H}(d) \enspace .$$

Unfortunately, HFE as described up until here turns out to be insecure. In particular, it is vulnerable to a direct algebraic attack involving efficient Gröbner basis algorithms. That's why you need at least one of the modifiers - (minus) or v (vinegar). It makes sense to use both. A good right-hand rule is $a + v + \mathsf{log}_2 D \geq 15$.

Minus means that some polynomials are dropped from the public key. In particular, the decomposition now involves a forgetful operator $\pi : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^{n-a}$ that leaves the first $n-a$ components intact but drops the remaining $a$ ones: $$\mathcal{P} = \pi \circ T \circ \varphi^{-1} \circ \mathcal{F} \circ \varphi \circ S \enspace .$$ In order to generate a signature, the signer has to choose the value of the missing polynomials. This is no problem as a random choice will suffice.

Vinegar consists of adding $v$ vinegar variables. During signature generation, the value of these vinegar variables is also chosen at random, after which what's left to do is to invert the regular HFE system. Instead of finding a solution to the linear $o \times o$ system (as was the case for UOV), now one must find the preimage by factorizing the HFE polynomial.