I am aware that one-way functions (OWF's) are the core of many of the primitives in symmetric crypto, in the sense that many cryptographic primitives in the private-key setting can be constructed from these.

On the other hand, in Multivariate Public-key Cryptography the goal is to find trapdoor functions of the form $F = (f_1(x_1,\ldots,x_n),\ldots,f_m(x_1,\ldots,x_n))$ where each $f_i$ is a quadratic multivariate polynomial over a finite field (say $\mathbb F_2$). However, the main assumption and motivation for this is that

A uniform function of the form $F = (f_1(x_1,\ldots,x_n),\ldots,f_m(x_1,\ldots,x_n))$ where each $f_i$ is a quadratic multivariate polynomial over a finite field is a one-way function.

Given this and the initial discussion, we would have already a symmetric world from multivariate polynomials, without additional effort. Have someone looked at these primitives? how would they be? evaluating at polynomials is extremely efficient but, would these primitives be efficient as well? If so, why aren't these already deployed?

  • $\begingroup$ I laughed at "without additional effort". :D $\endgroup$
    – fkraiem
    Mar 12, 2017 at 5:30
  • $\begingroup$ @fkraiem I'm glad someone found it funny at least :) what I mean is that the theory for constructing many primitives from OWF's is already developed, so we only need to come up with a reasonable OWF and feed it into this "machinery". Of course, this would require effort, but not the same effort than the one needed in order to construct these primitives from scratch. This is why I wrote "without additional effort" in italics. For instance, there are many (failed) efforts in MPKC to construct digital signatures. What would we get if we create one using the (provable) constructions from OWF's? $\endgroup$
    – Daniel
    Mar 12, 2017 at 16:03

1 Answer 1


You might look at the stream cipher QUAD invented by Berbain, Gilbert, and Patarin.

It uses the complexity of a multivariate quadratic map as the basis for its security. A drawback of this and other multivariate quadratic map crypto systems is the space needed to store a large random quadratic map.


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.