Mayo

Mayo is a signature scheme which builds upon the Unbalanced-Oil-And-Vinegar (UOV) scheme.
We have a trapdoored multivariate-quadratic (MQ) map $P:{\mathbb{F}}_q^n\to {\mathbb{F}}_q^m$, i.e. $x\mapsto (p_1(x),\dots ,p_m(x))$ where each $p_i$ is a homogeneous polynomial of degree 2.
Its corresponding symmetric bilinear form is defined as $P^{\prime }(x,y):=P(x)+P(y)+P(x+y)$.

The trapdoor, called the oil space $\mathcal{O}$, is an $o$-dimensional subspace of ${\mathbb{F}}_q^n$ on which the map $P$ vanishes, i.e. $P(o)=0$ for all $o\in \mathcal{O}$.

In UOV, a signature for some message is created in the following way:

1. Choose some $v\in {\mathbb{F}}_q^n$, called the vinegar.
2. Compute a message digest $t\in {\mathbb{F}}_q^m$ of the message
3. Solve the linear system $t=P(v+o)$ which is equivalent to $t-P(v)=P^{\prime }(v,o)$
4. The signature is $s=v+o$

For Mayo, $o<m$ which means that the above linear system does not have a solution in general.
Therefore a new “whipped up” map $P^{\ast }:{\mathbb{F}}_q^{kn}\to {\mathbb{F}}_q^m$ is constructed in the following way:
$$P^{\ast }(x_1,\dots ,x_k):=\sum _{i=1}^k{E}_{ii}P(x_i)+\sum _{1\le i<j\le k}{E}_{ij}{P}^{\prime }(x_i,x_j)$$
The parameter $k$ is chosen such that $ko\ge m$.
In this way proceeding like above, the linear system will have a solution with high probability.
The invertible matrices $E_{ij}\in {\mathbb{F}}_q^{m\times m}$ for $1\le i\le j\le k$ are called emulsifier matrices.

A signature in Mayo is generated analogously to UOV with the only difference that you have to choose $k$ many vinegars $v_1,\dots ,v_k$ and solve the linear system $t=P^{\ast }(v_1+o_1,\dots ,v_k+o_k)$.

For more information refer to the official webpage.

Parameters format

• n : number of variables in the MQ-map
• m : number of components in the MQ-map
• o : dimension of the Oil-Space
• k : Whipping-parameter s.t. $ko\ge m$
• q : number of elements of the underlying field ${\mathbb{F}}_{q^n}$ (in our case always $q=2^4=16$)
• $\{E_{ij}{\}}_{1\le i\le j\le k}$ : invertible “emulsifier”-matrices in ${\mathbb{F}}_q^{m\times m}$.
  Each line corresponds to one emulsifier-matrix and each inner list is a row of the matrix.
  Each entry is an element of ${\mathbb{F}}_q$, represented as an decimal integer.
  The Big-Endian binary representation of this integer corresponds to the coefficients of the polynomial in ${\mathbb{F}}_q\simeq {\mathbb{F}}_2[X]/(f)$, where $f=X^4+X+1$.
  For example: $13_{10}=1101_2=X^3+X^2+1$

This list of emulsifier matrices will be arranged in the following way to a 2-dimensional array (same as in the official specifications):
$$\left(\begin{array}{ccccc}{E}_{k-1}& E_{k_2}& \dots & E_1& E_0\\ & E_{2k-2}& \dots & E_{k+1}& E_k\\ & & \ddots & ⋮& ⋮\\ & & & E_{\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)-1}& E_{\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)-2}\\ & & & & E_{\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)}\end{array}\right)$$

• $\lambda$ : security parameter, length of the seed and half the length of the message digest.

Public key format

Since the $p_i$ are homogeneous polynomials of degree 2, they can be described by the following matrices $P_i\in {\mathbb{F}}_q^{n\times n}$:
$$p_i(x)=x^t\cdot P_i\cdot x$$
Moreover they can be chosen as upper triangular matrices:
$$P_i=\left(\begin{array}{cc}{P}_i^{(1)}& P_i^{(2)}\\ 0& P_i^{(3)}\end{array}\right)$$

The given public key file contains:
Always three lines, seperated by an empty line, containing $P_i^{(1)}$, $P_i^{(2)}$ and $P_i^{(3)}$ as a list of lists where each inner list is a row of the corresponding matrix.

Flag encoded into the Oil-Space

For the key-recovery challenges, a secret flag $m$ has been embedded into the Oil-Space $\mathcal{O}$ in the following way:

• Encode $m$ into $\lfloor o\cdot n/2\rfloor$ bytes (UTF-8).
  Each byte can be represented by two elements of ${\mathbb{F}}_q={\mathbb{F}}_{16}$.
• Write the nibbles into an $o\times n$ matrix $O$ from left to right, top to bottom.
  Check if $O$ has full rank.
• Enumerate the oil-space, i.e. compute $x\cdot O$ for all $x\in {\mathbb{F}}_q^o$, and sort the vectors lexicographically.
• The positions of the rows of $O$ (starting index 0) will be published.

If you were now able to recover a different basis $O^{\prime }$ of the oil-space, you can enumerate the Oil-Space, sort it lexicographically, find the vectors of the original basis via their positions and decode them into the flag.

Link to reference Sage code to extract (unembed) a secret message from a recovered private key