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?


1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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