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+y)-P(x)-P(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}$.

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
• q : number of elements of the underlying field ${\mathbb{F}}_{q^n}$ (in our case always $q=2^4=16$)

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