1
$\begingroup$

If we note all multivariate schemes restrict themselves to polynomials of degree 2.

I was wondering why they do it. After looking on the internet, I came to know that they do it for the efficiency.

My question is how working with degree 2 is more efficient?

$\endgroup$
4
$\begingroup$

In multivariate schemes, the secret key is a ``simple'' multivariate polynomial with some structure. The public key is obtained by wrapping the secret key in random linear maps. The resulting multivariate polynomial representation is very dense and unstructured to anyone without the secret key, meaning that any possible monomial would occur with high probability (depending on the field size). That means, storing $n$ such polynomials would require $O(n\binom{n}{d})\approx n^{d+1}$ coefficients, where $n$ is the number of variables / outputs and $d$ is the degree. The same value determines time complexity of encryption, as one has to go through all the coefficients in the public key to compute the ciphertext.

As you can see, degree 2 schemes already have cubic complexity in the number of variables.

$\endgroup$
1
  • $\begingroup$ Thanks. Nice explanation. $\endgroup$ – A B Dec 2 '20 at 7:19

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.