# The MQ Problem and Our Path towards Noise-free and Practical FHE

### About OpenTrust Lab

OpenTrust Lab is pioneering the next generation of Fully Homomorphic Encryption (FHE) through groundbreaking cryptographic schemes and high-performance infrastructure.
See https://opentrustlab.xyz for more details.

In this work, we explore a path towards noise-free and practical FHE based on the multivariate quadratic (MQ) problem.

## 1. The MQ Problem and Its Variants

At a high level the multivariate quadratics (MQ) problem wants to find a solution vector of size $n$ of a multi-variate polynomial system of size $m$ each of which has degree $2$.
More formally, it is defined as follows.

**Definition 1.1** (The general multivariate quadratics (MQ) problem[^YDHTS15]) For integers $n, m$, define the following equations:
\begin{align*}
&f_1(x_1, \dots, x_n) = \sum_{1 \leq i \leq j \leq n} a_{1ij}x_i x_j + \sum_{1 \leq i \leq n} b_{1i} x_i + c_1 = d_1\\
&f_2(x_1, \dots, x_n) = \sum_{1 \leq i \leq j \leq n} a_{2ij}x_i x_j + \sum_{1 \leq i \leq n} b_{2i} x_i + c_2 = d_2\\
&\vdots\\
&f_m(x_1, \dots, x_n) = \sum_{1 \leq i \leq j \leq n} a_{mij}x_i x_j + \sum_{1 \leq i \leq n} b_{mi} x_i + c_m = d_m
\end{align*}
where $a_{kij}, b_{ki}, c_k, d_k, k \in [m], i,j\in[n]$ are integers, find $x_1, \dots, x_n$ such that all the equations above hold.

**The homogeneous version of MQ.**
For homogeneous MQ,
there are only degree-2 terms.
In other words,
$b_{mi}, c_k, d_k, \forall k\in [m], i \in [n]$ are all zeros.

**Homogeneous MQ with fixed length.**
Further, let $\vec a_m := (a_{mij})_{1 \leq i\leq j \leq n}$, we say an $w$-length homogeneous MQ if all $\vec a_m$ has at most $w$ non-zero terms.
In other words,
$f_m = \sum_{z \in [w]} a_{m, w}x_{w_i}x_{w_j}$ where $w_i, w_j \in [n]$.

**Higher degree multivariate polynomial solving.**
MQ naturally extends to a higher degree.
Now, instead of having a degree of at most $2$,
each polynomial as degree $D > 2$
(e.g., when $D = 3$, the polynomial has terms $x_i^3$,$x_i^2x_j$, $x_ix_jx_k$).
Since our scheme relies on MQ being hard,
we omit the details for high degrees.

## 2. On the Hardness of MQ

The hardness of MQ highly depends on the parameter setting of $m, n$.

- When $m \ll n$, the problem can be solved in polynomial time (see [^CHMT14] and its prior works for details).
- When $m \approx O(n)$, the problem is deemed the hardest and the known constructions take exponential time to solve it[^YDHTS15].
- When $m = \epsilon n^2$ for some $0 < \epsilon \leq 1/2$,
the cost of solving the problem is $n^{O(\frac{1}{\sqrt{\epsilon}})} = n^{O(\frac{n}{\sqrt{m}})}$[^KipSha99].
- When $m \geq \frac{n(n+1)}{2}$,
the problem can be transformed into linear equations and thus be solved in $\mathtt{poly}(n)$ time.

## 3. Our Path Towards Noise-free and Practical FHE via MQ

We envision a path towards a noise-free and practical Fully Homomorphic Encryption (**PFHE**) scheme by leveraging the MQ problem.
In our proposed scheme,
the secret keys would be $x_i$'s (i.e., the variables in the MQ problem) and
the public keys (including the evaluation key for homomorphic operations) would be the $f$'s (i.e., the equations in the MQ problems).
We note that our scheme relies on homogeneous $w$-length MQ instead of the general,
but to our knowledge, there are no asymptotically better attacks on this form of MQ than the general MQ.

For the parameters, our scheme lies between $m = O(n)$ and $m = \epsilon n^2$.
Therefore, we conservatively use the attack for $m = \epsilon n^2$,
and estimate our parameters using the attack of complexity $n^{O(\frac{n}{\sqrt{m}})}$.
Note that this is still super-polynomial as long as $n = \omega(\sqrt{m})$,
and this is indeed the case in our construction.

**Quick note about using multivariate crypto to realize FHE.**
We would like to note that Craig Gentry,
who first realized FHE in 2009,
mentioned that multi-variate crypto is a potential future direction for FHE in his talk in Eurocrypt 2021, titled *A Decade (or so) of fully homomorphic encryption*.
Our scheme is the first to make a solid step towards realizing it.

Stay tuned for our upcoming work that will provide more details of our **PFHE** construction and its security analysis.

[^YDHTS15]: T. Yasuda, X. Dahan, Y.J. Huang, T. Takagi, and K. Sakurai. MQ challenge: Hardness evaluation of solving multivariate quadratic problems. Cryptology ePrint Archive, Report 2015/275, 2015. https://eprint.iacr.org/2015/275.

[^CHMT14]: C.M. Cheng, Y. Hashimoto, H. Miura, and T. Takagi. A polynomial-time algorithm for solving a class of underdetermined multivariate quadratic equations over fields of odd characteristics. In M. Mosca, editor, Post-Quantum Cryptography - 6th International Workshop, PQCrypto 2014, pages 40–58, Waterloo, Ontario, Canada, Oct. 1–3, 2014. Springer, Heidelberg, Germany.

[^KipSha99]: A. Kipnis and A. Shamir. Cryptanalysis of the HFE public key cryptosystem by relinearization. In M. J. Wiener, editor, CRYPTO’99, volume 1666 of LNCS, pages 19–30, Santa Barbara, CA, USA, Aug. 15–19, 1999. Springer, Heidelberg, Germany.