2
$\begingroup$

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?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.