In this question, I'd like to discuss the security of the last transformation $T$ employed in the construction of a MV-scheme. MVCrypto is based on solving a system of polynomial equations, but eventually, those polynomials are constructed by a linear combination of $T$ and a vector represententing an univariate polynomial in $F_{q^n}$ with coefficients in $F_q[x_1,\cdots, x_n]$. The following construction illustrates a typical description, where $\alpha : F_{q^n} \mapsto F_{q^n}$ is the transformation function (i:e Matsumoto-Imai) that changes the coefficients of $x'$ that are multivariate linear polynomials to multivariate non-linear polynomials. Note that here $v_s,v_t=[0]_n\in F_q^n$. \begin{equation} S,T \in F_q^{n \times n}, \quad x=(x_1,\dots,x_n)\in F_q^n \\ x'=S\cdot x \\y'=\alpha(x')\\y=T\cdot y' \end{equation}

Matrices are very useful since we can represent $F_{q^n}$ as $F_q^n$: the n-dimensional vector space over $F_q$. So $x'$ can be viewed as a polynomial with coefficients that are linear combinations on $x$.

$$x'= \sum_{i=1}^{n}(\sum_{j=1}^{n} S_{i,j}\cdot x_j)y^{i-1}$$

The attacker has $n$ multivariate polynomials and their evaluation on $x=(x_1,\cdots,x_n)$. If he finds out the transformation $T$, he could attempt to invert $\alpha$ to obtain $x'$ and finally, $x$. My intuition tells me that an attacker can find a pair $z\in F_q^n, T'\in F_q^{n\times n}$ s.t satisfies $T'\cdot z = y$. As an example, consider the following case where $V=F_5^2$:

$T=\left( \begin{array}{cc} 1 & 2 \\ 3 & 1 \\ \end{array} \right)$ $y'=(x_1x_2-1,x_1^2x_2+3)$

$T\cdot y' = y = (x_1x_2+2x_1^2x_2, 3x_1x_2+x_1^2x_2)$

It's pretty straightforward to recover $T'=T$ and $z=(x_1x_2,x_1^2x_2)$ since $y$ contains coefficients that are $n$ sums of the same $n$ factors, here $n=2$. Note that $z\neq y'$ but in this case is not hard to "bruteforce" until reaching the correct one.

EDIT: It's important that you note that $S$ and $T$ are interchanged in my example, $S$ is the first affine transformation and $T$ is the last one, however, in literature you found this to be the opposite. So the remark is that this question is about the last transform applied in the construction.

Question: Is there any information that describe an inversion of this construction, not by solving the polynomial eqs. but inverting the maps?


Almost a year since I posted this question, back then I was starting the study of the field. Now I can answer myself:

The security of both affine transforms $(T,S)$ relies on the IP2 assumption defined in the Isomorphism of Polynomials. Plus, if the private polynomial $\mathcal{F}$ is known there are other implications, like finding $T$ or $S$ would reveal the other affine transform.

This is, any multivariate scheme where $F,S$ or $F,T$ is known gives us the ability to break it. When $F$ is not known, as usually, we could obtain $T\cdot S$ as a matrix if both are linear transform instead of affine, and the linear part of $F$ is the identity matrix. From here nothing else can extracted, from the moment, in my study.

Regarding IP1, it can be broken when $F$ is known, or when $F$ is unknown by quering an oracle $n$ times with the canonical vectors $\overrightarrow{e_i}$.

Besides other techniques to strip out $T,S$ exist, i.e: when the characteristic is not $2$ and both transforms are linear.

There is more work not published in literature that I've discovered, i.e: the special structure of matrices $S$ that make the private polynomial invariant in a way that we can revover $T$, and more techniques that the audience must await for.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.