# The mathematical similarity and difference between code-based PKE and multivariate DSS

In code-based public key encryption schemes, a public key is formed by matrix-multiplying 2 linear matrices to the left and right side of a easily decodeable error-correcting code, so that it'll be difficult to extract useful information that may be used to decrypt ciphertexts.

In multivariate digital signature schemes, a public key is formed by compositing linear equation systems to the inner and outter parts of a easily solvable multivariate (usually quadratic) equation system, so that the resulting composition cannot be easily reversed.

From my understanding, the composition with linear systems is the biggest similarity between code-based PKE and multivariate DSS, and I wonder:

1. Is there any other aspect where code-based and multivariate cryptosystems are similar?

2. What are the important differences between code-based and multivariate cryptosystems?

Multivariate schemes tipically work with a central polynomial map $$\mathcal{F}(X) : F_2^n \mapsto F_2^m$$ which is a quadratic map that defines $$m$$ quadratic equations on $$n$$ variables. Then select $$T,S$$ as invertible affine transformations. The public key $$P(X) = T \circ F \circ S(X)$$ is written as $$m$$ quadratic forms in $$n$$ variables over $$F_2$$.
However, as every Quadratic Form $$q_i(X)=X^T Q_i X$$ can be linearised using Tensors, this is, a dot product of $$\overline{q_i}(x \otimes x)$$ where $$\overline{q_i}$$ is the $$n^2$$ vector reshape of the matrix $$q_i$$.
Then rewrite the public key as a $$m \times n^2$$ matrix $$\overline{P}$$ where the $$i$$th row encodes the $$i$$-th columns of the quadratic forms. This is a rectangular matrix which doesn't allow an attacker to compute the input value $$X$$ from the output $$Y$$. From here the goal is to either attempt to solve by obtaining the affine transformations $$(T,S)$$ which we refer to the Isomorphism of Polynomials ($$\mathcal{IP}$$), solving the underlying non-linear quadratic system over $$F_2$$, which is a subinstance of the PoSSo problem, called the $$\mathcal{MQ}$$ problem or studying the MinRank $$\mathcal{MR}$$ problem.
For example, an HFE public key can be computed using pure Linear Algebra, without working in Polynomial Rings and Finite Fields. Either deriving the Quadratic Forms as I did here or using Tensors. But you still need to apply Berlekamp's to find roots over $$F_q$$.