In general it's hard to calculate the roots of a given polynomial $P(x)$. But the other way back calculating the coefficients is much easier (Vieta's formulas).

If this is a one-way function, is it possible to create a public-key cryptosystem based on these facts? Or does it already exist?

  • 7
    $\begingroup$ Actually, it is easy to compute the roots of a polynomial $P(x)$ defined over a finite field. $\endgroup$
    – poncho
    Mar 19 '14 at 16:58
  • 1
    $\begingroup$ Ok, but what about non-finite fields? $\endgroup$ Mar 19 '14 at 17:07
  • 8
    $\begingroup$ With an infinite field, $P(x)$ may not be expressible in a fixed number of bits (or, depending on the field, even a bounded number of bits). That puts rather a crimp in the cryptographical applications. $\endgroup$
    – poncho
    Mar 19 '14 at 17:44

First, note that having a one-way function is far from enough to construct a public-key encryption scheme (a famous result of Impagliazzo and Rudich actually shows that it is impossible to construct public key schemes from one way functions only).

Second, cryptographic constructions which aim at being implemented at some point rely on the hardness of problems over finite sets in general (this is a vague statement, but quite intuitive). Over finite fields, finding roots of a univariate polynomial is easy.

However, a problem related to what you ask about is that of the difficulty of solving systems of equations of multivariate polynomials. This problem is hard (it is even NP-hard) and was used as the underlying cryptographic assumption for the construction of public key cryptosystems and signatures schemes. Unfortunately, no public key cryptosystem built on such assumption has survived cryptanalysis (to my knowledge); every attempt was proven insecure at some point (this is not true, however, for signature schemes).

Hence, even though it might be possible to construct public key cryptosystem based on problems related to finding roots of (multivariate) polynomials, this has proven to be at least a very hard task. See e.g. the Wikipedia article on Multivariate cryptography for more details on the topic.


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.